First look at Dynamixel

I received the Dynamixel I had ordered as a sample of what they can do. So far I'm impressed.

Accessories

The servo itself is a boring thing to receive. It's small plastic box. But I also, wisely, bought all the accessories that I needed to make it go.

First, I needed a way to give it instructions. Instead of spending my time trying to get my Arduino board to control it (which sounds like a real struggle), I bought a USB2Dynamixel adapter that allows me to control it from my computer. My final product will still be using a computer as its brain -- rather than simple robots that can be offloaded onto a little processor board -- so I suspect I might still be using this adapter in the final product.

The USB2Dynamixel is a chunky thing, as it provides an old-school serial port (I'm sure they have a technical name), a 3-pin plug for TTL Dynamixels, a 4-pin plug for RS-485 Dynamixels, and of course the USB plug for the computer. There's a selection switch on the side to activate one of the outputs.

Second, I needed power for the servo. Despite there being a power cable as part of the RS-485 connector, the USB standard doesn't supply enough juice to make the servo go. So I bought an external 12V power supply, like the kind you plug into a laptop (and, in retrospect, I probably just should have looked around for an old 12V supply that I'm no longer using).

So far everything sounds very organized and easy. But the people at Robotis really dropped the ball in one area: how you deliver the external power to the Dynamixel. There is no connector for it. No board. No dongle. No adapter. I had to build my own. Robotis knows this is necessary because they provide a quick drawing of what you need to do on their website. That's nice of them, as I wouldn't have known what to do otherwise, but they should just provide an appropriate adapter as part of the USB2Dynamixel package.

To get the power hooked up, I had to get out my soldering iron. Thankfully I found it, and it still worked. I had to cut one of the wires in a RS-485 connector, and attach the positive power supply wire to that (so that power is connected to the Dynamixel, but not the USB2Dynamixel). Then I had to strip a little bit of the wrapping on another wire, and splice in the ground wire from the power supply (so that ground is connected to both the Dynamixel and the USB2Dynamixel). Being a clumsy amateur, that splice was the ugly one and took me a while to get right. But in the end, my connections seem to work, and I didn't burn myself.

Here's a picture of my doctored RS-485 connector. I'm waiting for some electrical tape to arrive to make it look pretty and prevent it from electrocuting me. Note to others: get some shrink wrap sleeves to cover this mess instead of electrical tape.

Here's a picture of the USB2Dynamixel with the connector and the power supply and the Dynamixel. This is the whole setup.

Software

Robotis provides a free download of the software to manage and test your Dynamixel. Sadly it is for Windows only, but I have a Windows machine that still works. I believe there is a Linux SDK that I will have to investigate if I want to use the USB2Dynamixel in the final product, but Robotis says that the Windows software is necessary for configuration and firmware updates.

You have to select the correct COM port; the one that the USB2Dynamixel is being presented as. Then it has to search for your Dynamixel over the cable. I think it is just sending out "are you there?" messages to all the possible receiving addresses until it gets a response. Get a response it did.

The software then presents all of the status and settings for the device. There's actually a fairly long list of things there. Things like limits to how far/fast/hot it considers acceptable. Things like the accelerating and decelerating at the beginning and end of a servo move to make it smooth. Things like the current voltage, load, speed, position. And -- most importantly -- the current goal position.

If you change that goal position, the servo moves. They have a cute little software dial, and clicking your mouse on the dial makes the servo rotate to that position. Much more glamorous than my push-button Arduino controller.

Results

The speed of the Dynamixel seems about right. It was rated at 0.079 seconds per 60 degrees. This is the fastest of the Dynamixels (aside from one that is designed to be a wheel, and doesn't have much power). It rotates from -150 degrees to +150 degrees -- that's something to keep in mind for my arm design.

Strength is difficult to measure, as I don't have any attachments for the servo. I have the servo horn it comes with, which provides a way to screw it to your robot, but I don't have a robot yet. I'm attaching a piece of boxboard just so that I can see it rotate better. But until I find some material to make my arm out of, I don't have anything that can test the strength or measure its speed under load. But the specs say it's supposed to be 360 oz-inches (compare that to the 21 oz-inches for the cheap servo in my Arduino post).

Here's a video of it turning the cardboard. Whee.

So that's it for now. My first experience with Dynamixel has been a good one, and I plan to design the robot to use them.

Arduino

Continuing with my diversion into the robotic implementation of my vision, I bought a cheap and popular robot controller to play with. Arduino is an open-source hardware and software project for prototyping electronics projects. I've seen it mentioned a few times, so I decided to get my hands on one.

There are number of versions of their microcontroller boards. Their common features are USB communication with a computer for power and for programming, a microcontroller chip to run the programming, and a lot of input and output pins to connect various sensors and actuators.

I opted for the Mega2560 version because it happens to offer a second serial interface (the first one being used for the USB connection). If you've read my previous entry, you'll see that Dynamixel uses a RS485 serial communications protocol, so if I ever wanted to use an Arduino board to talk to a Dynamixel, it would be needed. I'm not sure I'll ever want to do that, as it isn't really designed for it. But I wanted that flexibility.

My first impression is that this thing is extremely easy to use. The open-source software offers a programming environment that is very similar to C, with extensions that make sense for programming hardware. It also comes with a huge number of samples that take you from a first timer to some complicated projects.

I wanted something easy. And I wanted to use a servo. So I bought a cheap beginners kit of electronics accessories for Arduino that included a cheap servo. This is of the analog PWM variety, and it lists its key specs on the side: 21 oz-inches and 0.12 s/60deg. So that's comparable in speed to the Dynamixels I am considering, but much much weaker in power.

I first used a sample program that blinked an LED on the board. Simple. Then I jumped in and used the code from a servo example to make my own modification. I want to control the servo with a pushbutton. When I push the button, it rotates to 90 degrees as fast as it can. When I let go of the button, it rotates back to its starting position. Here is the Arduino code.

// control a servo with a pushbutton

#include <servo.h>
 
Servo myservo;  // create servo object to control a servo 
                // a maximum of eight servo objects can be created 

// constants won't change. They're used here to 
// set pin numbers:
const int buttonPin = 2;     // the number of the pushbutton pin
const int ledPin =  13;      // the number of the LED pin
const int servoPin = 9;

// variables will change:
int buttonState = 0;         // variable for reading the pushbutton status
int servoAngle = 0;

void setup() {
  // initialize the LED pin as an output:
  pinMode(ledPin, OUTPUT);      
  // initialize the pushbutton pin as an input:
  pinMode(buttonPin, INPUT);     
  myservo.attach(servoPin);
}

void loop(){
  // read the state of the pushbutton value:
  buttonState = digitalRead(buttonPin);

  // check if the pushbutton is pressed.
  // if it is, the buttonState is HIGH:
  if (buttonState == HIGH) {     
    // turn LED on:    
    digitalWrite(ledPin, HIGH);  
    servoAngle = 90;
  } 
  else {
    // turn LED off:
    digitalWrite(ledPin, LOW); 
    servoAngle = 0;
  }
  // write the servo location
  myservo.write(servoAngle);
  // i'm worried about making the servo freak out
  // so give it a delay here so it doesn't get too many commands
  delay(50);
}

That's it. And it worked, first try. That's why Arduino is so great: I got it to work on the first try. Here's a little video of the setup (a hybrid of a push-button example and a servo example) and me pushing the button.

Yeah, I know it's not that exciting. But at least I have now used a servo. Check that box.

You can see how fast 0.12 s/60deg is. It's medium-fast. Not blinding. Probably fast enough for most of my ping pong tasks, but faster might be better. The servo has a very short arm on it, which makes it feel quite strong (probably about 21 oz worth!).

Anyway, that's all I've done with the Arduino for now. I have a Dynamixel on order, and will play with that next. I'll be controlling that over USB using their USB2Dynamixel adapter, instead of using a micrcontroller like this. At least for now.

Servos

I know I said I was going to focus on the image processing part of the problem first, but I couldn't help look ahead a little bit to the robot building phase. It's better to know now if this project is feasible, how much it will cost, and any design constraints that might be mitigated by image processing. And it's also fun, and mixes up my day a little.

So, never having built a robot before, I've been doing some reading and looking at some stores. The fundamental building block for robots is almost always servos. In construction, they are an electric motor, a set of gears to strengthen-but-slow the spinning of the motor, a feedback mechanism that can tell what angle the motor is currently pointed, and some electronics to use that feedback to control the spinning of the motor. From a functional perspective, you tell them where to point, and they point there and hold their position until you tell it to point somewhere else. I'm sure there are many nuances, but I can't be bothered with such petty details.

Important Specs of a Servo

There are two main specifications of servos that interest me: rotational speed and torque. Rotational speed is how fast the servo can change positions. Since my robot will have to move fast enough to hit a ball, speed matters. This is usually expressed either in rpm or in seconds-per-60-degree-rotation. They are easily convertible:

sec per 60 degrees = 10 / rpm
rpm = 10 / sec per 60 degrees

Torque is the turning strength of the motor. It is expressed in any of Nm (the metric version), oz-inches (the US version), or kg-cm (a bastardization of the two). If we consider a servo with 20 oz-inches of torque, it can hold a 20 oz mass against gravity at the end of a 1 inch arm from the servo. Or it could support a 1 oz mass against gravity at the end of a 20 inch arm. So you multiply the mass times the length of the arm to get the required torque. The metric version of Nm removes gravity from the interpretation and explicitly measures the force it can apply at the end of an arm (yay metric for making sense!). Now keep in mind that this is the limit of what the servo can support. If you have a 20 oz-inch servo supporting 10 oz at 2 inches, it won't actually be able to move the arm -- but it will keep the arm suspended, just fighting off gravity. Any more weight or length, and the arm will fall under the load. My point is that if you want the arm to actually move against gravity, you have to supply more torque than that. And, conversely, you can use less torque when moving the arm down, as gravity is pushing that way anyway.

Types of Servos

I see two types of servos: analog and digital. Analog is the most common and the most affordable. They tend to use PWM (pulse width modulation) as the way you tell it what angle you want. For example, hobby servos used in model airplanes typically turn to 0 degrees with a 1000us signal, to 90 degrees with a 1500us signal, and to 180 degrees with a 2000us signal. It is analog because the length of the pulse is translated into the position of the servo. These types of servos need relatively simple control electronics to create the pulses, but it's not so simple that you can just do it from your computer directly. Some sort of servo controller is necessary to produce these pulses, and then your computer can talk to the controller to choose the pulse width.

Digital servos are more expensive, but seem to be preferred for robotics. I'm not really sure why yet, but there is probably a reason. Instead of taking PWM pulses over a signal wire, they take some form of digital communication over a signal wire or wires, and the on-board electronics read the message, extract the degrees you wanted, and move the servo accordingly. This means that the servo controller is different: it has to be able to speak in the appropriate serial protocol, instead of a simple on-off pulse.

Dynamixel

There is a dominant brand in the robotics servo market: Dynamixel, made by Robotis. They make a variety of servos with different speed and torque specifications to suit your particular application. They communicate over a TTL serial line or a RS-485 serial line (honestly I'm not sure why they have two protocols as from a high-level they seem equivalent).

I'm going to list a few of the servos in the Dynamixel line, to give you an idea of the specs available. This is taken from the Trossen Robotics store, which seems to be a good resource.

Model	Speed (s/60 deg)	Torque (kg-cm)	Price (USD)
AX-12A	0.196	16.5	45
RX-24F	0.079	26	140
EX-106	0.143	107	500

This covers the three corners of specifications: the AX is cheap, the RX is fast, the EX is strong. Well, none of these are cheap. Here is a typical hobby servo for model airplanes and helicopters:

Model	Speed (s/60 deg)	Torque (kg-cm)	Price (USD)
Hitec HS-322HD	0.15	3.7	10

Much cheaper. But it also illustrates why Dynamixels are preferred: torque. The AX is 5 times more expensive but 5 times more torque. The EX is 50 times more expensive, but 25 times more torque.

Honestly there really aren't other brands of robot servos available. You can either try to use servos intended for a different application (like these model airplane servos), or you can use the Dynamixel line, intended for robotics, or you can have a fancy lab and build your own. My inclination is to stick with what other roboticists have decided makes sense, and use the Dynamixel line.

Since there isn't a one-size fits all servo, each joint will need to be evaluated to determine what speed and what torque is desired, and then I can choose the most economical servo to accommodate that. It also puts upper limits on the the speed (about 0.079 s/60) and torque (about 107 kg-cm). Well... torque can be improved by using two servos in the place of one servo. There are even pre-fabricated brackets to team two EX-106 servos together, effectively doubling the torque (at more than double the cost!). Speed is a little more fussy to multiply, but in theory it can be done by adding your own gears, sacrificing strength for speed. Honestly I don't want to do that if it can be avoided.

Conclusion

So it looks like I'm headed towards using Dynamixel servos. I don't own any yet, and I would rather know which specs I need before I run out and buy some. So in a future post I might work on a bit of the math to determine how fast and strong I need the arm to be.

Epilogue
I've ordered an RX-24F to play with. Sometime next week?

Where's the table?

Background subtraction has gone fairly well. It seems that it will be a decent way to find the ball. Making a good background model will reduce noise in the background. Stereo vision will make it easier to differentiate the ball from the opponent. Looking at consecutive frames will narrow down the possible locations for the ball. So I'm moving on to the next question: where am I?

I realized that even if I could identify the ball, I needed to know where it was in relation to the table and in relation to the robot. I'm going to assume that the table is stationary, that the robot's base is stationary, and that the cameras are stationary. All plus or minus some noise when the wind blows and the camera shakes.

So that means that this problem only needs to be solved once when setting up, and that solution should remain valid. I suppose I could force my setup to be rigidly measured. E.g. the robot base is 20cm behind the table at the center line, 30cm above the table, always. Yeah, that could work. In fact, I will probably do it that way first. But it would be nice if my robot could be placed in front of the table and figure that out for himself. After all, ping pong tables are fairly distinctive objects. You'd think it would be easy to identify the table in the image, apply some stereo math, and come up with the 3D model of where the cameras and robot are with respect to the table.

New Image

Here is the input image I've decided to work with. I've blurred my handsome face because I'm a privacy freak and because I'm embarrassed that my forehead looks like a ping pong ball. It has some challenging conditions: patches of bright sunshine in the background that gets reflected in the surface of the table. It's kind of a pain in the ass. It makes me think that maybe robot researchers resort to carefully controlled lighting and matte surfaces on everything. But I'm better than that. Maybe.

As a human, it sure seems easy to identify the table. Not a lot of ambiguity, despite the challenging conditions. So shouldn't a machine be able to do this easily?

Detect The Color Blue

If I'm going to be using color images (still to be decided), I should make use of the color information. My table is blue, which makes it stand out. Annoyingly my shirt is a similar blue, and my jeans are not far off. How do you even identify "blue" from an image?

I went to Matlab to experiment. Since blue is one of the RGB colors, it should be easy. However, in RGB space, if you want B to be lighter or darker, you have to add some R and G, because there is no "light/dark" element to it. "Light" happens when you have more of every color, "dark" when you have less of every color. Here's what I came up with. In short, the B channel has to dominate the other colors.

function blue = blueDetect(img)
% split the colors for clarity
r = double(img(:,:,1));
g = double(img(:,:,2));
b = double(img(:,:,3));
% calculate blueness
blue = (b - r*0.5 - g*0.5) ./ b;
% display the image, normalizing so that the most blue pixel is all the way red
image( (blue ./ max(max(blue))) * 64);

And here's what it looks like:

This uses Matlab's default "jet" color scheme: the more "hot" the color, the more "blue" I've decided it is. (I'll use this color scheme in other images but I'll be excluding the scale from now on.) So it was kind of accurate. You can apply a threshold to give a yes/no answer as to whether each pixel was blue. This is using 30% "blueness" as the cutoff:

I think this shows the real problem: some of the table isn't blue. Go back and look at the original image. On the far side of the table, the reflection makes it more white/gray than blue. My blue detector doesn't even think it's close. That's going to be a problem. A human uses other clues to decide that it was a reflection, but apparently that's not easy to do. It also seemed to get confused by the back of the paddle on the right of the image. The paddle is black. To a human, it's pretty clearly black. But I guess the way I calculate things, it's more blue than red or green, so it is bucketed as being blue.

I decided to make another blue detector. This time I decided to use abandon the RGB color space, in favor of HSV. That stands for hue, saturation, value. "Value" seems to be approximately equivalent to "light" vs "dark". I'm going to give you three images, with each of HSV and broken down, so you can see how they behave.

So the good news is that the table is a very consistent hue value. The bad news is that the background wall is almost the same hue. As is the cement below the table. But when you look at the saturation, you can see that the table is a very saturated blue, but the wall and the cement are not. So it seems that it might be possible to combine this information to identify the blue of the table.

I chose to do this as a probability distribution. I create a normal distribution for each of H, S, V that says what the mean value of "table blue" is, and how far it is allowed to stray from that ideal. When evaluating a pixel, I multiply the probability from each of the distributions together to get a combined probability of being "table blue". Here's the code.

function blue = blueDetect2(img)
% convert from rgb to hsv color space
imghsv = rgb2hsv(img);

% define the means and standard deviations in each of H S V
% hue is very tight around 39/64ths
hueMean = 39.0 / 64.0;
hueStd = 1.8 / 64.0;
% saturation is high but wide to account for glare and shadow
satMean = 42.0 / 64.0;
satStd = 11.0 / 64.0;
% value is high and wide (but this captures most of the image)
valMean = 47.0 / 64.0;
valStd = 8.0 / 64.0;

% calculate the probability for each pixel for each component
hueFit = normpdf( (imghsv(:,:,1) - hueMean) ./ hueStd );
satFit = normpdf( (imghsv(:,:,2) - satMean) ./ satStd );
valFit = normpdf( (imghsv(:,:,3) - valMean) ./ valStd );
% combine the three component probabilities together
allFit = hueFit .* satFit .* valFit;

blue = allFit;
% display the image, normalizing so that the most blue pixel is all the way red
image( (blue ./ max(max(blue))) * 64);

And here's the resulting image:

That seems to be better than the previous method. It is more sure about the table, and doesn't seem distracted by the paddle. There is less "blueness" on the wall or the rocks in the bottom right. Here is a thresholded image at 30% blueness:

Conclusion

This entry explored ways to identify the table via color. It was moderately successful, but the challenging image meant that it wasn't perfect.

I still haven't identified the corners of the table, which would be necessary for my 3D model. And there are many other approaches I could try, aside from color, to identify the table. I leave that for other blog entries.

OpenCV

After my first attempt at doing some vision processing in Matlab, I concluded there must be a better way. I don't want to rule out Matlab entirely. It seems that Matlab can be taken seriously for vision applications. But that would require buying the Toolbox that does that sort of stuff, and I'm not willing to put down the money on software that I might not need. I worry that anything I need to implement myself (as opposed to being built-in to the Toolbox) will be inefficient. Matlab is really only efficient for matrix operations.

OpenCV

It didn't take long to find OpenCV, which is an open source machine vision library. It implements many algorithms common in vision applications, and provides some of the framework to make C++ closer to the simplicity of Matlab. Since it does much of what the Matlab Toolbox does, and will allow me to write efficient custom implementations in C++, I think it provides more room to grow.

OpenCV was a bit of a pain to build from source. Some dependencies also had to be built from source, as the versions offered on my RHEL 6 machine were too old. It's been a week or two since I did the install, so I'm afraid I can't recount any of the details. In the end I got it installed and it seems to be working.

OpenCV also comes with Python bindings, which makes it more fun to do quick exploration work. I've been going back and forth between the two, depending on what I'm doing.

Background Subtraction

So, what can I do with OpenCV? I decided to stick with background subtraction for now. OpenCV has a more complicated approach to background subtraction, and that's probably a good thing since my quick Matlab approach had flaws.

There is more than one background subtraction algorithm in OpenCV, but I've chosen to use the one that seems the most popular and/or newest. That's BackgroundSubtractorMOG2. My vague understanding is that this method builds up a history of each pixel's color, and builds a statistical distribution around that history. Then, when you ask it to decide if a new value for that pixel is foreground or background, it compares the new value to the distribution. If it is too different from the historical distribution, it is flagged as being foreground. The MOG part is referring to a "mixture of gaussians", which means that each pixel's historical distribution is from one of a number of normal distributions. That's intended to capture different valid background states of the pixel. For example a pixel might sometimes have a leaf in it, and sometimes the leaf might have shifted out of the way, revealing the wall behind. Both of those should count as background, even though they are vastly different colors. Obviously I will need to do more reading if I want to understand it. It's available in this paper: Improved Adaptive Guassian Mixture Model for Background Subtraction.

MOG2 also has a built-in shadow identification. Again, I don't know the details, but it flags shadows as not being foreground, and it decides something is a shadow if it is an appropriately dimmer version of the same color.

This algorithm requires many more frames of input in order to decide what the background looks like, so I've had to feed it each frame to set up the algorithm. The following code does all this, and displays/saves the foreground image every 100 frames.

#include <iostream>
#include <cstdio>
#include <opencv2/opencv.hpp>

using namespace std;

void DisplayProgress(cv::Mat& img, cv::Mat& background, cv::Mat& foregroundMask, int frameindex)
{
 cv::imshow("Original", img);
 cv::imshow("Background", background);
 cv::imshow("Foreground Mask", foregroundMask);
 // process the foreground further to remove noise and shadows, etc
 // shadows are masked with value 127
 cv::Mat noShadowForeMask = foregroundMask & (foregroundMask != 127);
 cv::Mat smoothForeMask;
 cv::GaussianBlur(noShadowForeMask, smoothForeMask, cv::Size(11,11), 4.0, 4.0);
 cv::imshow("Foreground Blurred", smoothForeMask);
 cv::Mat binarySmoothForeMask = (smoothForeMask > 64);
 cv::imshow("Foreground Blurred Binary", binarySmoothForeMask);
 // extract the foreground picture
 cv::Mat forePic;
 img.copyTo(forePic, binarySmoothForeMask);
 cv::imshow("Fore Picture", forePic);
 // save the foreground
 const char* filenameFormat = "/home/me/src/ping/out%03d.png";
 char namebuff[256];
 sprintf(namebuff, filenameFormat, frameindex);
 cv::imwrite(namebuff, forePic);
 // wait for user to hit a key before continuing
 cv::waitKey(-1);
 cv::destroyAllWindows();
}

bool LoadImage(const char* filenameFormat, int frameIndex, cv::Mat& fillMeWithImage)
{
 char filename[256];
 sprintf(filename, filenameFormat, frameIndex);
 fillMeWithImage = cv::imread(filename);
 return (fillMeWithImage.data != NULL);
}

int main(int argc, char** argv)
{
 cv::Mat img;
 cv::Mat foreground;
 cv::Mat background;

 cv::BackgroundSubtractorMOG2 bgSub(200, 10.0, true);

 const char* filenameFormat = "/home/me/src/ping/movie1png/movie1-%03d.png";
 for (int frameindex = 1; /*infinite*/; ++frameindex)
 {
  if (!LoadImage(filenameFormat, frameindex, img))
  {
   cout << "Can't find frame " << frameindex << " so assuming we reached end of movie" << endl;
   // display last progress at last image in the movie
   // re-read the last image that existed
   --frameindex;
   LoadImage(filenameFormat, frameindex, img);
   bgSub.getBackgroundImage(background);
   DisplayProgress(img, background, foreground, frameindex);
   break;
  }
  // learn the new image
  bgSub(img, foreground);
  cout << "Added frame " << frameindex << " to background subtraction processor" << endl;
  // display progress occassionally (every 1.66 seconds at 60 fps)
  if (frameindex % 100 == 0)
  {
   bgSub.getBackgroundImage(background);
   DisplayProgress(img, background, foreground, frameindex);
  }
 }

 cout << "Done" << endl;
 cv::destroyAllWindows();
 return 0;
}

I'm doing a little extra processing on the foreground decision it makes. I ignore shadows as not being foreground (thank you built-in functionality). I then blur the true/false mask, and then make it true/false again. Effectively I'm looking for pixels whose neighbors are foreground, but that weren't foreground themselves. This nicely prevents lone pixels in the middle of a foreground blob from being excluded unfairly. It also expands the region marked as foreground, which might be a bad thing.
For convenience of comparing these results to Matlab, I've run it on the same movie I used in that blog post, and manually grabbed the foreground pictures from the same frames I used in that post (instead of looking at each 100'th frame). And here they are, in the same order they appear in the Matlab blog entry (stupid me: not in chronological order).

Of course, this is just the background subtraction, and ignores the findBall aspect. No red crosses in these images. But the subtraction seems to be fairly good, and the extra work I've done (blurring/thresholding) has removed the noise of the table and bush shimmering. It doesn't have some of the drawbacks of my Matlab method, like looking only at increases in intensity.

It still would suffer from requiring good contrast with the background -- I've run it on my second video and had contrast problems. In fact, here is a raw image from a frame in that other video. Where's the ball? Even a human would have a hard time finding it without the context of where the ball was last frame. Yep, it's that little slightly-lighter-gray smudge in the middle. So contrast is still a problem.

Efficiency

Running background subtraction in OpenCV has not proven to be very efficient. With the ~1MP images I'm working with, it was taking much more than 1/60th of a second to process a frame. I'm estimating it was processing about 25 frames per second. This would mean that it can't be run in real time without improvements.

I have some ideas there. The first is using Region of Interest ("ROI") capabilities of a camera, or even on the software side. If you know the thing you are interested in (i.e. the ball) is in a particular region of the picture, only process that region. If ROI is implemented on the camera, that means the camera will only send pixels in that region (which also saves on bandwidth!). I imagine I can find the table and the ball once, then in each incremental frame I could have a very good guess about where to look for the ball. I might only need to process the whole image again if I lose track of the ball.

The second idea is to run the update on the background model (the mixture of gaussians) only periodically. Or, better yet, run for a large number of frames with background only. That would parameterize it to recognize the background (leaf, not leaf, etc) without getting confused by a stationary-but-foreground object, like the opponent's body. Then running the model on live action frames might be faster without the update to the model. The OpenCV code doesn't seem organized in a way that makes that possible, but that's what's good about open source: I can change it.

Conclusion

I conclude that OpenCV is going to be a great tool, but at the same time BackgroundSubtractorMOG2 may or may not be appropriate for me. It is compute intensive to the point that I can't run this way at full speed. My results in Matlab were almost as good for background subtraction (and could easily be reimplemented in OpenCV).

So in this update I made progress only in that I was able to use my new tool: OpenCV. But at least it is progress.

First attempt

This is my first attempt at doing some computer vision work.

The Camera

Since I haven't really decided what I need yet, I used the supplies and tools I had at hand. So I went out and recorded some video on my Canon Rebel T3i. That's an SLR camera -- not a video camera per se, and certainly not a high-performance video camera. But it can shoot 60 fps at 1280x720 (a.k.a. 720p) and save it to a memory card. It cannot stream a live feed in real-time to a computer. It was a bright day for this outdoor shoot, which was in the shade. That, combined with the overall quality of the camera and the lens, meant that the video turned out fairly well. I chose to shoot from behind me and to one side, above the table, which made it easy to keep the table in the frame.

Here is the footage that I'm working from. It has been webified down to 30 fps and compressed -- the original was in a higher quality .mov format at 60 fps.

Extracting Frames

With that video captured, I came back inside and started the processing. It was easy to copy over to my computer, as Ubuntu recognized the camera as a mass storage device, and I copied the .mov file. The file was 67MB. Simple.

I had some trouble getting the replay to work in some Ubuntu players. VLC seemed to do the best job, so that's what I've been using ever since. It plays nicely.

I wanted to extract individual frames from the video, so that I could attempt to identify interesting features in it. To do that, I used the ffmpeg/avconv tool, available in the Ubuntu repository. This is what I did:

ffmpeg -i movie1.mov -r 60 -f image2 pngofmov/image-%03d.png

This created a separate png file for each frame of the movie. With 7.5s of footage, I get about 7.5*60 = 450 frames. Each frame's png is about 1.3MB, for a total of 585MB -- much bigger than the original .mov.

Processing

I used Matlab to do this processing, as a) I have it available, b) I understand how to use it, c) I didn't know any better. Note that I do not own the Image Processing Toolbox, so I'm using the base Matlab package.

The good news is that Matlab makes it easy to load images, display them, and treat them as 3D matrices of numbers. That meant that it took me just a few minutes to get started and under and hour to complete this whole task.

Background Subtraction

I chose to focus on a handful of images from the movie, to see if I could identify the ball in them. To do this, I had the idea of background subtraction: subtracting one image from another to identify the differences. If you subtract an image with only background in it from an image with action on top of the background, you should be left with just the action. Sounds easy.

Seriously, this is how much code this takes in Matlab:

img291 = imread('image-291.png');
imgbase = imread('image-060.png');
imgdiff = img291 - imgbase;
image(imgdiff);
print('-dpng', '291minus060.png');

Well, here is my first attempt.

Background Image

Image With Action

Foreground Through Subtraction

Wow! That actually worked! The ball clearly appears, as does my arm with a paddle. Now, it might be hard to see in this web-sized image, but there is additional noise in the image. There is movement in the bush in the background and even the edges of the table seem to be shimmering enough to cause the odd pixel to light up. But the overall effect is pretty clearly a success.

Finding the Ball

How do I turn that into an algorithm to find a ball? Well, after a little bit of trial and error (and a little googling for how to create a circle mask), I came up with this little function. It searches for the greatest intensity increase that is in the shape of a circle of a particular size.

function circxy = findBall(imgbase, img)
    % do the subtraction
    imgdiff = img - imgbase;
    % average the red,green,blue pixels to get grayscale
    imgdiffgray = mean(imgdiff,3);
    % define a mask/kernel with a 12-pixel radius circle in the middle
    % the kernel has +1 inside the circle and -1 outside the circle
    crad=12;
    ix=sqrt(2*pi*crad^2);iy=ix;cx=ix/2;cy=cx;
    [x,y]=meshgrid(-(cx-1):(ix-cx),-(cy-1):(iy-cy));
    circmask = ((x.^2+y.^2) < crad^2);
    circkern = circmask * 2 - 1;
    % apply the mask to every location in the grayscale difference
    circfind = conv2(imgdiffgray, circkern,'same');
    % find the location where the kernel fit the best
    [circx,circy] = find(circfind == max(max(circfind)));
    circxy = [circx,circy];

So how does it do? Let me show you:

Yep, that's a red cross on top of the ball. It found it, and I would argue quite accurately. Here's a zoomed in look.

Yep, that's pretty accurate. Was it a fluke? I ran it with three more images. Here are the results, zoomed in on where it placed the red cross.

Those red crosses are all on the ball.

I left this session feeling pretty good about how I was doing. In fact, I still feel pretty good about how I did. But, looking back on it later, I have a few concerns with this approach, even though it worked on all four of the frames I tried it on.

• This required an initial background-only image. I'm not sure if that is realistic or not. For now I won't worry about it.
• My image subtraction approach looks only for where a particular color has increased in intensity. If something gets darker, it is excluded from the difference (it actually gets a negative value in the raw matrix, and matlab displays this as black). Perhaps an absolute value subtraction would be more appropriate?
• This means that my method is very dependent on the contrast between the ball and the background. If I had a pale background -- say that light gray wall -- the contrast would be lower, and it would stand out less. It's possible that my circle-finding kernel wouldn't choose it as the strongest match.
• My circle kernel is a predefined radius. Admittedly, I looked at an image or two, and decided it was about 12 pixels in radius. This varies depending on how far the ball is from the camera, and all these test images have the ball a fairly similar distance. (On the plus side, we might be able to use the radius to approximate its distance from the camera!)
• Motion blur is clearly visible in some of these test images. The ball ceases to be circular, and instead turns into a round-ended rectangle (the path a circle sweeps as it moves). This is most obvious in the last image, where the ball must have had its greatest velocity. It still found the ball in this image, but I suspect it was less certain. (On the plus side, we might be able to use motion blur to estimate the velocity of the ball!)

Epilogue: I have run this algorithm on another set of photos, and it wasn't so successful. Those images had more movement (an actual whole person) and had patches of bright sunshine in the background. The first findBall I tried identified my forehead as the most likely ball in the image.

Quantity of data

I've been doing some looking at cameras. I'll have plenty to say on the cameras themselves later, but first I want to take a look at the sheer quantity of data that I'm proposing to capture.

Let's say we want 120fps. There seems to be an industry standard to use multiples of 30fps until getting into the many-hundreds. So I'm just rounding up the 100fps I asked for in my previous post.

Let's say we want 1 megapixel. That's a 1024x1024 image, if it was square. It probably won't be square, but that's a good approximation of 1280x720 or similar resolutions. I think this is a decent resolution with which to capture a moving ball without the fancy zooming used by the Ishikawa Oku Lab.

Let's say we want 24 bits per pixel. I'm least confident about this requirement. But that's enough bits to give an RGB image with 8 bits for each color, or 0 to 255 values for each color for each pixel. That's a pretty common image format, I believe, so I think it is reasonable. I'm avoiding greyscale intentionally: I think that the color of the table (blue) vs the lines (white) vs the ball (white right now, but I'm thinking of changing to orange) vs the paddles (red and black) is going to be important.

So what does that add up to, in terms of the quantity of data produced?

120 * 1024 * 1024 * 24 = 3,019,898,880 bits per second = 2.88 Gibabits per second

But wait! I intend to use stereo vision, so that's two cameras: 5.76 Gbps.

Since I want to process this on a computer, and I need it done in real-time, this much data has to be sent to my computer in a constant stream. I would also have to be able to process this much data, otherwise there is little point in sending it to the computer.

Transmission Medium

Focusing on the transmission first, does this introduce any problems?

USB 2.0, the most prevalent USB format in use today, is 480 Mbps, well below what I need. So something like a USB webcam, if it were to offer the frame rate and resolution I want, wouldn't be able to send all that data to me.

There are three other common formats used by fancy cameras: GigE, USB 3.0, Camera Link.

GigE is just using standard networking. It can run over a standard $5 CAT 6 cable, and can even be switched and piped around using a $30 network switch. The cameras have some built-in electronics to convert their data into UDP to be sent over the network. On the receiving end, you just need a standard GigE network port, and then some software to interpret it. This means that, after the camera itself, there is almost no cost, and that is very appealing. Of course there is a problem with this: bandwidth. GigE is so-named because it can transmit 1 Gbps. Since I'm proposing 2.88 Gbps per camera, it won't all fit on the wire. So GigE is eliminated if I want to stick to my specs (but notice that if I went to 8 bits per pixel -- greyscale -- it would fit!).

USB 3.0 is the newest USB standard. It is still rare, but is starting to be adopted. I believe one of my computers at home supports a single USB 3.0 plug, and I imagine that there are other motherboards out there that would accept two of them. USB is also cheap when it comes to accessories, because it is a standard format. I can buy cables for $5. So far it sounds good -- but what about bandwidth? Well, it's adequate: USB 3.0 is specified to handle 5 Gbps of traffic. So that would comfortably hold a single camera's data. I would need one cable for each camera, and my computer would have to be able to handle them both simultaneously.

Camera Link is designed just for cameras, which sounds promising. It comes in a few different "sizes", which are really just using multiple cables cooperatively. The cables are not very common, really only used by deep-pocket researchers and industry. I seem to find them starting at $200 each. They also will require a card in my computer to receive the signal over the cable, to get it into computer memory. Those are apparently called "frame grabbers" and I haven't found prices on them yet... I expect they are > $500 and possibly into the many thousands. On the plus side, the bandwidth is there. Camera Link Base (one cable) is 2040 Mbps, and Camera Link Full (two cables) is 5.44 Gbps. Yes, I see that two cables is more than double one cable, but they do something fancy to make that happen. So I could fit a single camera on a Full cable. If my requirements were lowered a little, it might fit on a Base cable.

Computer Side

So once I get the data to the computer, how realistic is it to process this information?

Well, first consider that in some cases it will have to move across the PCIe bus from an add-in card. Good news: PCIe 2.0 (which I imagine is most common) can transmit 8 Gbps with 2 lanes, which is not at all hard to find.

So now we can get it to the motherboard itself, and presumably into RAM. DDR3-800 SDRAM can be accessed at 51.2 Gbps, so memory doesn't seem to be a problem. We can't keep it in RAM for any significant length of time, or else we're going to need a lot of RAM. So basically we want to use frames as they come and discard them immediately.

What about CPU speed? If we had a 3.6 Ghz 8-core machine (which I don't have at home, but I could if needed), we have a total of 3.6 billion * 8 = 28.8 billion clock cycles per second to use. That's 240 million clock cycles per frame. If I wanted to do any operation on a frame that required calculating something for each pixel (any convolution operation seems to fall into this category), that's 240 cycles per stereo pixel. That's pretty tight to do anything fancy and I'm going to need to pay attention to this and look for ways to reduce CPU load.

Conclusion

This exercise has brought me to conclude that if I want 24-bit color 1 megapixel images at 120fps, I'm going to need USB 3.0 (easy and cheap, but new) or Camera Link (expensive and specialized, but established). I'm also going to have to pay close attention to the demands I am placing on the CPU.

Note: source for all the bandwidth numbers was Wikipedia, here.