In one of the recent posts I have covered the topic of camera calibration a little. But that was not really interesting. Tons of very good books have been written about that. Today we’ll look into keeping your cameras in calibrated state after they’ve been calibrated instead.

Suppose you have a 3d-tracking system that uses about 20 calibrated cameras installed in some crowded place like bank office or shopping mall. In such places calibrated cameras have a tendency to become uncalibrated sometimes, mostly due to vibrations caused by factors like construction work or cleaning. What should we do about that? Obviously, we should recalibrate cameras whose position or orientation has been changed (or change position and orientation back to original). But how can we find out what cameras should be calibrated again? Should we hire a man who’ll check image on every camera every day? Fortunately, we shouldn’t.

Camera decalibration can be detected automatically

What we have to do is to save snapshot from camera at the moment its extrinsic parameters were estimated. Then the following algorithm can be used to check for decalibration:

1. Extract something like SURF features from the saved snapshot and current camera image.
2. Match extracted features.
3. If not less than 10-15% of the matched points have the same pixel coords, camera is OK. Otherwise, it seems to be decalibrated.

As you can see, this algorithm is fully automatic and can be run, for example, every hour for every camera. It is also quite robust to presence of some temporary objects like humans in both images because it requires only small amount of matches to have the same pixel coordinates. It seems that it works bad (or doesn’t work at all) only in cases when there are very few good features available (for example, when camera looks at the white wall). But in those cases it’s very hard to detect camera decalibration even for human. One can also make this algorithm robust to illumination changes by using some lighting-invariant point descriptors or by image preprocessing.

OK, we have determined that camera has become decalibrated. And we also have old camera position, orientation and point matches between current and old camera images. It seems that we can automatically determine new camera position easily. Or can’t we?

Camera can not be recalibrated automatically

And here is why. Of course, there is a 3d reconstruction algorithm that takes a list of coordinates of matches together with camera intrinsic matrix and returns transform from old camera view space into view space of the new one (together with 3d coordinates of the points). Unfortunately, it can calculate transform and 3d coordinates only up to scale. Neither coordinates of the matched pixels nor intrinsic matrix contain enough information about the scale of you scene. Are you measuring everything in meters? Or in inches? You need more information (like real 3d coordinates of one of the matched points) to rescale algorithm results. But you don’t have them. So the reconstruction algorithm gives you pretty much nothing (well, it gives you correct camera orientation, but you can’t use it without rescaled translation).

It’s interesting that I’ve failed to find any papers covering the topic of decalibration and recalibration although it’s quite important for some practical computer vision applications. Should I write a short paper about it by myself?

Now, as it was proposed by Ilia, I’m using subversion to hold some local files. How can subversion help with local file scenarios? For example, sometimes you need to share some files (or even complex directory trees) between your computer and laptop. It can be some research stuff: papers, slides, code etc, or, probably, university lectures and assignments. It’s rather cool when you have a way to merge your changes from different sources without carefully checking out what files were added, deleted or (the worst case) modified (probably, by more than one source).

But the most awesome thing is not the SVN itself, many of you are already familiar with version control systems. The most awesome thing is that you don’t need to install and configure SVN server for that. Just install Tortoise SVN, right click on some folder and choose “Tortoise SVN -> Create repository here”. You can then use “file://” prefix to refer to this repository (UNC paths are also supported).

Unfortunately, according to Tortoise SVN documentation, using “file://” for remote repository access is not recommended. That is because in fact you should give read-write access to the repository files (that are hidden when using SVN server) to every repository user. That can easily lead to corruption of those files, especially in cases when two or more users are accessing repository simultaneously.

Anyway, that use case is still OK for single user access scenarios. Even if you have only one computer, you can use it to have version log of programs you are developing. It helps a lot when new bugs are introduced during program evolution. Nevertheless, TDD helps better :)

People often understand complex things better when good examples are provided. But, unfortunately, many mathematicians prefer abstract explanations like “so, Slut(x) and Drunk(x) obviously implies Sex(me, x)” instead of just saying “I’m pretty sure I’ll have sex with that drunk chick tonight”. That’s why I want to create a list of math application examples to some real-world things that are familiar to most people. It, probably, can make math more interesting and, of course, more comprehensible. And, I’m going to start from the graph theory because it seems to be rather clear even for people far from math. So, here we go.

Click to read more ...

I’ve just updated my RoboZZle solver. There are two major changes:

• I’ve fixed bug with program execution loop detection using approach proposed by Igor Ostrovsky there. So it can solve “Count the tiles“-like puzzles now.
• I’ve added the whole new solving approach based onto evolutionary algorithm (implemented using AForge.NET library). It is not very useful just for now, but still can solve some complicated puzzles. I’ve used eaten star count as a fitness function for program. So, if there is only one or two stars on the field, this approach works just like random search. But if you know correct path for your robot (it is obvious in many puzzles), you can mark it all with stars using field editor integrated in the solver, giving your guess to the evolutionary algorithm. The main problem with this approach is that in many puzzles correct program is very different from the program that can collect almost all the stars on the field. I need better fitness function, and probably, some other crossover and mutation ops. Currently chromosome is just a concatenation of all the program functions’ code. Mutation operator changes color or operation at random position of the chromosome. 2-point crossover exchange operations between two chromosomes.

It's totally true that choosing new president for your country is quite important decision. And it's also true that some people are clever, and some are not. I understand all that democracy stuff, but why should we care about some junky opinion as much, as about the Noble Prize laureate's one. Solution of this problem is well known in machine learning. It's called weighted voting and consists of assigning weights to the each voter and then combining votes together with weights being taken into account.

At this time I'm participating in a contest provided by Russian search engine called Yandex. In the contest participants should build an algorithm which can rank web search results by relevance well, using features of both found documents and search query itself. Later I'll post about my contest experience, but today I want to write about something else.

While solving such tasks you always have to deal with large amounts of data in different formats. It often involves implementing some converters etc. For example, in the Yandex contest I've tried to apply SVMRank algorithm to the given data using SVMLight first. That forced me to write a small program for sorting input data by query id because of SVMLight requirements. Then, of course, I've added ability to restore original data order to my program because results are checked by the contest automatic checking system which knows anything about me reordering the data. Then I've decided to apply PCA to the input data before applying SVMRank algorithm (warning! due to the unusual feature value distributions result was terrible!). MATLAB contains freely available PCA implementation, so I've added ability to export data to format supported by MATLAB and import it back to my program. Then I repeated the following sequence of actions several times (for each number of selected PCA components): convert data to MATLAB, load attributes, apply PCA (fortunately, first 3 steps should be done only once), save first K attributes, convert back to SVMLight format, sort by query id, learn SVMRank model. Then I did the same for the test data except of replacing model learning with rank prediction and original order restoring. Of course, I could make a script from that action sequence and run it several times, but it has it's own drawbacks. For example, I know nothing about integrating external applications with MATLAB and learning that stuff can only increase amount of time required to perform the whole process.So, that's all boring, dreary and it distracts you from the actual task. What can we do about it? I've just thought: why there is no special operating system for researchers, scientists and engineers that can make their lifes much more easier. Here is a short list of what I'd like to see in it:

Primary (related to the previous paragraph)

1. Math engine (some kewl mixture of MATLAB and MAPLE) should be integrated with OS environment. I want ability to run any math command in any shell opened and get result immediately (well, it depends on command). And all the calculated math data should be accessible through math engine from any other OS part.
2. There should be comfortable math engine API available for most popular programming languages.
3. There should be some standard for all the data types used in the math engine.
4. All the external math algorithms should be integrated in the OS math engine. All that algorithms should use the same math data types provided by math engine (see 3).

Secondary (all the ideas that came to my head while writing "Primary" section):

1. I'd like to see some semantic relationship database integrated to the OS where you can hold dependencies between papers, researchers, lectures, presentations, data sets, experiment results etc (take a look at the MSR Research-Output Repository Platform). For example, it would be rather kewl to visualize references between articles related to some research area as a graph. It allows you to filter the most important works quickly and opens many other possibilities.
2. There should be some useful network interaction mechanisms. For example, I can stream experiment results in real-time mode to my colleague who will immediately visualize it. Or I can implement some math algorithm using OS math engine and ask my colleagues to share their computing capabilities with me. Or I can submit it to some computing server and then stream required data to it. And all of it completely transparently. And there should be, of course, some mechanism for relationship synchronization between network nodes.
3. And, finally, it would be a pleasure to have some comfortable LaTeX editor and compiler with all the necessary stuff.

At least, unification of the data formats and math engine will help with exchanging data, prototypes, algorithms etc between researchers. Nowadays it turns into "Let's try to build it" game very often.
Well, it would be nice to hear other ideas and opinions. And then, may be, someone will read this post, get inspired and 5 to 7 years later new operating system will totally change all the scientific community =)
By the way, my team in the Yandex contest has the same name as this blog.

Due to interest in my RoboZZle puzzle solver of project developer Igor Ostrovsky (who by the way has a blog with tons of really interesting stuff) I’ve decided that it would be interesting to continue development. The first thing I made was fixing small nasty bugs and improving solver UI. Then I’ve created project page on google code. Now anyone (who wants) can participate in developing this amazing (as I think) application.

Currently solver has at least one unsolved algorithmic problem with detecting infinite loops when testing generated problem. Program state history tracking with state hash set is used in current implementation. State is represented as a vector of five numbers S=(X, Y, Direction, Function, Instruction). When solver detects that current execution state has been seen before, it decides that program had entered into infinite loop and interrupts it. This algorithm detects loops very fast but, unfortunately, sometimes it can interrupt a correct program. For example, in the problem “Count the tiles” robot should rotate consequently five times on the one of the red tiles. And the state before the fifth rotation is exactly the same as before the first one. That’s why my solver can’t solve that task for now. I should think about implementing more correct but still efficient way of execution loop detection. Any suggestions are welcome!

We have also plans to make more handy puzzle image recognition. Screenshot should be accurately cropped in your favorite image editor first when using current implementation. That can’t be called “comfortable”. Ability to recognize robot position and orientation will be added too.

Everyone who just wants to see the solver in action can download binaries here (.NET 3.5 required).

Updated solver UI:

Recently my friend Ilya has shown me another puzzle-like project which is completely different from Project Euler. It’s called RoboZZle. Each problem consists of a field colored with three (or less) different colors with stars placed on it and little robot. You should write programs for that robot to help it collect all the stars. Robot command language is very simple: there are only rotation and step commands. Complexity comes with the fact that subroutines and recursion are allowed, but number of subroutines and instructions in each subroutine is limited. Puzzles there differ from very simple that can be solved in 30 seconds to really complex taking about an hour.

After solving near 40 puzzles I though that it would be really fun to make an automatic solver for RoboZZle. I’ve coded simple algorithm that uses backtracking to generate different programs of specified length and check if generated program is a solution to puzzle. After few simple optimizations made (like no right rotation followed by left or no three consequent rotations in the same direction) it has shown really good speed. I’ve solved then about ten puzzles from Moderate and Hard categories using my solver. To simplify puzzle input process my friend Ilya wrote a simple program converting screenshot of a puzzle from web-site into textual description.
Currently my solver can’t solve problems with more than 9 free slots available and all the three colors presented on the field because of huge size of program space. I hope I’ll improve it later in some ways and put on a google code.

Today I've found an interesting site AllLookSame.com. There is a test on web page that allows you to check your skills in recognizing Chinese, Korean and Japanese people faces. And I've failed that test. I've guessed only 4 of 20 people. Less than a quarter. Maybe computer can do it much more better?