ARPool London Preparation

I’ve spent a great deal of time this past month getting ARPool ready for our trip to London UK to be on Stephen Fry Gadget Man. So much has happened it is going to be tough for me to remember it all!

It begins by testing all the code I wrote after OCE which actually essentially worked on the first try a minor miracle! After confirming that ARPool 2.0 ran we spent the next week improving the calibration process. I added much better debugging visuals and several new functions including a really handy calibration test function which tests the mapping from image coordinates to projector coordinates by drawing test points on the table so you can confirm the calibration accuracy.

With calibration looking pretty good I moved onto the ARRecogntion Class. This class is the work horse of ARPool all the vision algorithms are in here. I started by cleaning the code and adding documentation – you heard right in ~4 years of the project no one has documented it… I made a nice comment block above each function clearly explaining its purpose, its inputs (in detail such as if the image is rectified or not etc.), outputs. There is also a debugging tips section.

I made many small improvements to ARRecognition and a few major ones – notably I re-did the motionDetection algorithm which detects when the shot is finished restarting the process. I also worked on the detectShot algorithm to fix a bug where another ball next to the cue ball would cause a shot to not be detected. The first major change was in the detectBalls function where I added code for detecting balls whose blobs are joined after background subtraction. The final algorithm here is quite slick, if the blob is bigger than a single ball a matchTemplate is ran to find the 2,3,4 etc. best balls in the image. A max search is performed on the output of matchTemplate and the location is recorded and then a black circle is drawn centered at the point before running another max search. This ensures the balls that are found are not overlapping at all. This change made a big difference in the performance of the system – especially since we could now be more relaxed on the background subtraction threshold since ball blobs joining is no longer an issue. I also added some code for the special case of finding the balls when they are set up for the break shot.

That explanation was kind of brutal and if you’re actually reading this your probably like code so here is the source!

/************************************************************************
/   segmentBallClusters
/
/   Input: blobs image and the contour to be segmented
/          numBalls - the number of balls the contour should be segmented into
/          centers - a vector of ball centers not an input but an output via reference
/
/   Return: the ball centers in the vector by reference
/
/   Purpose: Segment a blob into a number of balls, gets called by detectBallCenters
/            when a blob is the the area of nultiple balls, e.g. two balls are touching
/
/   Debugging Tips: Check the blobs image saved by detectBallCenters
/                   watch what the erode is doing
/                   imshow the "results" image
/
************************************************************************/
void ARRecognition::segmentBallClusters(cv::Mat &blobs, std::vector<cv::Point> &contour, int numBalls, std::vector<cv::Point2f> &centers)
{
    // draw the blob onto the blobs image
    std::vector<std::vector<cv::Point> > contours;
    contours.push_back(contour);
    cv::drawContours(blobs, contours, -1, cv::Scalar(255,255,255), CV_FILLED);

    // get an ROI of the blob we need to segment
    cv::Rect rect = cv::boundingRect(contour);
    cv::Mat roi = blobs(rect).clone();
    cv::cvtColor(roi,roi,CV_RGB2GRAY);

    // template for the ball
    cv::Mat templ = cv::Mat::zeros(m_ball_radius*2,m_ball_radius*2,CV_8U);
    cv::circle(templ, cv::Point(m_ball_radius, m_ball_radius), m_ball_radius, cv::Scalar(255,255,255), CV_FILLED);

    cv::Mat result;
    cv::matchTemplate(roi,templ,result,CV_TM_CCOEFF_NORMED);

    cv::Point offset(rect.x, rect.y);

    if(numBalls != 15)
    {
for(int i = 0; i < numBalls; i++)
{
    // find the maximum
    double minVal;
    double maxVal;
    cv::Point minLoc;
    cv::Point maxLoc;
    cv::minMaxLoc(result,&minVal,&maxVal,&minLoc,&maxLoc);

    // add ball center at max loc
    cv::Point center(maxLoc.x + offset.x + m_ball_radius, maxLoc.y + offset.y + m_ball_radius);
    centers.push_back(center);

    // remove this max by drawing a black circle
    cv::circle(result,maxLoc,m_ball_radius,cv::Scalar(0,0,0),CV_FILLED);

    //cv::imshow("result",result);
    //cv::waitKey();
}
    }
    // numBalls == 15 -- Special case for the "break"
    else
    {
cv::erode(roi,roi,cv::Mat(),cv::Point(-1,1),(int)m_ball_radius/2);
cv::findContours(roi.clone(), contours, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_NONE);

std::vector<cv::Point> polygon;
double precision = 1.0;

while(polygon.size() != 3)
{
    //std::cout << "precision" << precision << " num polygon vertices" << polygon.size() << std::endl;
    cv::approxPolyDP(contours[0], polygon,precision,true);
    precision += 0.1;
}

// add offset to polygon points
for(int k = 0; k < 3; k++)
{
    polygon[k] += offset;
}

cv::polylines(blobs,polygon,true,cv::Scalar(0,255,0),3);

// interpolate ball centers
centers.push_back(polygon[0]);
centers.push_back(polygon[0] - 0.25*(polygon[0] - polygon[1]) - 0.25*(polygon[0] - polygon[2]));

centers.push_back(polygon[0] + 0.7 * (polygon[1] - polygon[0]));
centers.push_back(polygon[0] + 0.5 * (polygon[1] - polygon[0]));
centers.push_back(polygon[0] + 0.3 * (polygon[1] - polygon[0]));

centers.push_back(polygon[1]);
centers.push_back(polygon[1] - 0.25*(polygon[1] - polygon[2]) - 0.25*(polygon[1] - polygon[0]));

centers.push_back(polygon[1] + 0.7 * (polygon[2] - polygon[1]));
centers.push_back(polygon[1] + 0.5 * (polygon[2] - polygon[1]));
centers.push_back(polygon[1] + 0.3 * (polygon[2] - polygon[1]));

centers.push_back(polygon[2]);
centers.push_back(polygon[2] - 0.25*(polygon[2] - polygon[1]) - 0.25*(polygon[2] - polygon[0]));

centers.push_back(polygon[2] + 0.7 * (polygon[0] - polygon[2]));
centers.push_back(polygon[2] + 0.5 * (polygon[0] - polygon[2]));
centers.push_back(polygon[2] + 0.3 * (polygon[0] - polygon[2]));
    }

    return;
}

The biggest change I made was to re-do the ball identification system. The current one was not working great and was very messy code wise which I didn’t like. I wanted to make it cleaner, easier to maintain and I wanted it to use the OpenCV machine learning module. I gathered a bunch of training and test data and started playing around with the data. I found great success with cvBoost classifiers. The new system is a bit different as it employs different classifiers for different purposes. First a classifier picks the cue ball from all the other balls (1 vs all) and another does the same for the 8 ball. Another classifier classifies the remaining balls as either stripes or solids before finally 2 separate classifiers assign actual numbers. This is great because each level is a fail safe. Our primary concern is finding the cue ball properly, next is the 8 ball. The actual number is the least important but it is good to know if the ball is a stripe or a solid.

With ARRecognition in the best shape its ever been in I started investigating the graphics code and why our drawImage function was not working properly any more.  I wasted the whole first afternoon just trying to find a solution worked out for me online – it was one of those things where I just didn’t feel like diving in and as a result I got no where. The next day though I had motivation again – I started the graphics code from scratch adding back one function at a time. This turned out to be a really good thing to do because now I understand the graphics code. I was also able to consolidate all the opengl code from about 4 different .cpp files into a single file, now all the drawing code was in one place brilliant! I added the same documentation as I had for ARRecognition – man this project is starting to look very nice!

All of this work has been very satisfying for me but it makes me a bit sad that no one truly appreciates all the vast improvements I have made except for me. The system looks the same when it is running but the code behind is so much more reliable and easy to work with. I’m sure it will pay off in London!

read more

The Arch Linux Plunge

I finally took the plunge. It’s Thanksgiving in Canada and I am taking a nice relaxing break from work by installing Arch Linux for the first time. I suppose its not what most people do for a break from work but hey I am a huge nerd what can I say. I’d been interested in Arch Linux for quite a while and this weekend was just what I needed to get started.

The install process was actually fairly smooth, there were a few bumps here and there but as people always say the Arch forums are fantastic and they helped me more than a few times. So I was working through the install, which is all terminal in case you haven’t done it, while simultaneously installing a new version of Android on my phone when I realise that I needed to leave the house in 15 minutes to get to Thanksgiving dinner on time. I pause, I really want to finish this install but I don’t know how much is left and I don’t want to have to start over. That’s when I thought about exactly what I had done and how I was doing it and realised that I could simply resume at this exact point later but booting from the live usb and mounting the install partition under /mnt and then running chroot again. It was a cool moment and a bunch of stuff just kind of clicked in my brain – Linux level up!

I returned the next day and finished the install fairly quickly (and by finish I mean I can boot into my Arch install using GRUB after it boots it is still just a terminal). I continued on and installed X11 and company. For my window manager I wanted to go with openbox because it is super fast and lightweight kind of how I envision my laptop being. It was neat to see how all of these separate programs work together. I added a file explorer and graphical text editor.

I want to stop here and just briefly mention that throughout this whole install I’ve been slowly falling in love with Arch’s package manager pacman. It is truly amazing! That’s pretty much all I got there.

I was surprised at how quickly I was able to get my system up and running – what was weird was that it was surprisingly easy to get the various tools and stuff that I wanted but what was really hard and still unfinished is getting all the various widgets we take for granted like the wifi menu and battery indicator in the panel etc. Basically my system works, has all the tools I want, is blazing fast but looks like shit lol. Project for another day!

* edit * discovered ArchBang, it is basically Arch except with a few more common things installed like the network manager and battery widget. They also have already put some time into configuring openbox so it actually looks good. I’m glad I went through the Arch config once but in the future I may just cheat and start with ArchBang!

read more

My First OpenCV Commit

Contributing to open source has long been on my to do list, I actually get chirped a lot for my love of open source, anyways I recently finally made the leap and commited some code to OpenCV.

I’d long been on the look out for something good to add to OpenCV and then one day it hit me – I’d had this utility function for cv::PCA that I had been using a lot in my own work that would be a real nice addition to OpenCV. Having decided on what I was going to contribute I started reading on how to go about this and admittedly I was pretty confused what actually helped me figure it out was the generic git hub tutorial, I am a bit embarrassed to say but I am still pretty amateurish with source control but I’m getting better!

So I figure out the process and cloned myself a copy of the OpenCV repository and got right to work. It was a pretty simple addition really, what it does is gives another option for how to create a PCA space. Previously your only option was to specify the exact dimension of the space my addition allows the user to specify the percentage of variance the space should keep and then figures out how many principal components to keep thus deciding the dimension of the space.

It works by computing the cumulative energy content for each eigenvector and then using the ratio of a specific vectors cumulative energy over the total energy to determine how many component vectors to retain. You can read more about the specifics on the PCA wikipedia page. Here is the source code:

    // compute the cumulative energy content for each eigenvector
    Mat g(eigenvalues.size(), ctype);

    for(int ig = 0; ig < g.rows; ig++)
    {
g.at(ig,0) = 0;
for(int im = 0; im <= ig; im++)
{
    g.at(ig,0) += eigenvalues.at(im,0);
}
    }

    int L;
    for(L = 0; L < eigenvalues.rows; L++)
    {
double energy = g.at(L, 0) / g.at(g.rows - 1, 0);
if(energy > retainedVariance)
    break;
    }

    L = std::max(2, L);

After coding my new feature and I wrote a nifty little sample program (you can find it at OpenCV-2.4.3/samples/cpp/pca.cpp) that adjusted the number of dimensions according to a slider bar and showed the effect on reconstructing a face!

Affect of retained variance in a PCA subspace on data reconstruction

I was all ready to go so I pushed to my git hub account and made my pull request to have the code merged. I received an email back the next day with some feedback – a few of my commit messages were junk, I hadn’t realised that this messages would tag along with my code oops! Git rebase to fix that issue. I also had not provided documentation or added tests for my new code – I didn’t even know about the test module and didn’t realise the I could edit the documentation silly me. I wrote the tests first which was kind of fun actually and pretty straight forward as I was able to modify the existing PCA test. The documentation was a bit more out there - I had never worked with sphinx before but luckily I was able to get by simply looking at how stuff was done.

Pull request #2, this one looks much better much more professional  I am pretty proud of it. I wait, I wait I hear nothing, there is a few other pull requests sitting there too. I figure hearing nothing might be good maybe it is because there are no glaring errors and they are carefully reviewing my work. Finally about 2 weeks later pull request accepted! I contributed to OpenCV yay! A bit later on one of the dev’s who I am internet friends with told me to check the OpenCV meeting notes – I got a shout out!

There I am - “a small yet useful extension to PCA algorithm that computes the number of components to retain a specified standard deviate has been integrated via github pull request.”

Also here is a link to the OpenCV page where my documentation can be seen:

http://docs.opencv.org/modules/core/doc/operations_on_arrays.html?highlight=pca#pca-pca

read more