Structure in the flow

As a theme of this blog is information overload, I need to point this out: an email charter, a set of principles for senders to respect to make email overload less of a problem. Here’s a blog post on its elaboration.

The fact is, a lot of information overload could be dealt with at the source, if the sender/publisher had more care for the time of the recipient/audience. Conventions such as these, or as netiquette, need to be made explicit to get more adoption.

I’ve also made two small updates to pages:

• On the page about monitoring pages for changes, I now recommend using Firefox SiteDelta (or other locally installed software) as Google web page monitoring feature has been cancelled
• For code snippet organization, I now point to this discussion at StackOverflow which is a nice overview of the wide range of options people use

As I said in the previous post, the first assignment in that computer vision course I took was to write an image stitching program. The basic idea is to take a series of pictures by rotating around the point where the camera is located. Then you find how each “maps” to the others and “stitch” them into a single coherent panorama.

At first I thought this couldn’t make sense for a first foray into CV algorithms and/or would take a gargantuan amount of time. Turns out only the second part was right, but mostly because I had to learn to use Mathematica and program in OpenCV along the way. And the hardest part was already done for us by either of these tools, anyway: finding correspondences between pictures.

The basic principle, as I said, is to find corresponding points between pictures. To do that you need to identify “keypoints”, basically points that look unique yet can be identified in another picture to find matches, even if in the other picture they’re slightly different. There’s a whole world of research on how to do that, but in our case it boiled down to either using SIFT or SURF features in Mathematica and OpenCV. Then some “distance” is used to find points that match between images. It measures how much the region around keypoints differ between potential matching points.

Once you’ve got these matches between pictures, supposing for the moment they’re all correct, if the pictures were taken “right” you can find a transform matrix H (an homography) such that, if x is the coordinate of a point in the first image, Hx gives the coordinate of the point in the second.

So, skipping some details about weeding out bad matches, what I did was find an homography between pairs of consecutive images, and bring everything back into the coordinates of the central image. Starting from these, say:

I get this:

Cropping to keep only the central part:

Now I will concede my C program probably doesn’t have all the gizmos of other commercial options (notably if you look at the full size version above, you’ll see problems stemming from auto lighting on the camera), but hey, for a first assignment I was pretty impressed with the result. (And it turns out it was actually a pretty good first assignment, as those transformations and keypoint finding operations were fundamental for the rest of the course).

(As a last technical point: to filter out bad matches, we used RANSAC and other constraints on distances (in my case the first match must be much better than the second one).)

I’ve been taking a few graduate courses at Université de Montréal in the past two years, but the last one, the computer vision course, was by far the one with the most “showable” (mighty Google says that’s a word) projects. I’ll be posting later on the first project, a basic image stitching app. For now, I’ll just leave this here:

It’s an example result from my term project. In a nutshell, skipping the technical:

• I take a couple of pictures with a camera for which I know some parameters, notably focal length;
• In the scene there’s this augmented reality tag which helps me find out where the camera is in each pose;
• I find corresponding points between images to create a (sparse) 3D point cloud of the object;
• I then use MeshLab to get a mesh (I only have points, I need triangles) and then find some “good enough” textures for the triangles;
• I then use the 3D model that comes out of all this and overlay it on the original scene, so the model ends up being … well where it should be in the first place.

I wrote this using ARToolkit+ and OpenCV. Reprojecting onto the original image is done with OpenGL.

Some technical details for those who are into this kind of thing:

• I pre-calibrate the camera model with OpenCV calibration routines and a “chessboard”;
• Getting the camera position from the detected tag is simply decomposing an homography between the tag plane and its image, which happened to be something we did for another course work;
• I find corresponding points with SURF, and filter correspondences with epipolar line constraints found from camera poses, among other filters;
• I first find correspondences between image pairs, and then merge them correspondences from all pairs using an algorithm I cooked up;
• Finding a texture for each triangle involves finding a “good” image to project the triangle onto, then building a huge map of the textures for OpenGL from the extracted bits of the original images.

I know the tracking’s pretty bad (I had to hack ARTookit+ which would return false positives at times) and the model is far from the reconstruction quality you’d get with less sparse techniques (another student in the course tackled reconstruction with structured light, for example, and had ~2 million points… I get ~2000), but hey, it (kinda) works and uses only a webcam (for the example shown above).

Maybe at some point I’ll get around to making the tracking smoother, at least. And to posting a more detailed demo of the app itself. It shows a bunch of fun stuff about the reconstruction process, like epipolar lines and camera positions for each pose.

I’ve gone through many posts along the lines of “oh I haven’t got time for this blog”, here’s another. Well in fact it’s the last one, as I won’t see this as a “blog” anymore. Let’s call this a “website”, like in the good old days when everything was edited manually and the concept of “timeline” wasn’t as important (Why would content like this be ordered chronologically anyway? It was trendy, I guess…). I’ve thought about doing this for a while, found a few hours to do it this morning, so here we go!

I’m still using WordPress, as it’s a good content management system anyway. Also, it’ll still allow for changes to be tracked in the sidebar.

I also changed the theme to something slightly more traditional; I find it easier on the eyes. It’s my first blog’s theme, in fact.

Just a note concerning two small new features I added to my Javascript speed reading (RSVP) app:

• You can now change the speed using your keyboard’s up/down arrows keys
• Text and background colors may now be selected using a color picker (based on JsColor)

These were features some users asked for either on the blog or in the comment form in the app. Thanks for the feedback!