Synthetic Training Data

One of the recent breakthroughs in computer vision was the use of synthetic data to train effective recognition systems. The most remarkable example is the work of Shotton et al. from Microsoft Research Cambridge, who trained the kinect human pose recognition system using more than a million of synthetic images, generated by rendering fake humans using 3D software.

That's perfectly possible mainly because the computer graphics industry has been working on generating 3D humans with realistic appearance for cinematographic productions and games. Clothing materials, hair, shapes and so on, are easily simulated in 3D. So, generating 3D human poses is a well establish and well understood procedure, and it make sense to generate synthetic data for this kind of problem.

What about medical images? Can we generate synthetic images simulating various medical conditions? It sounds a bit weird, right? Well, during the SIPAIM 2011 in Bucaramanga, Juan Antonio, one of the invited speakers from Spain, was giving a tutorial on how medical images are captured and generated, specially using Magnetic Resonance Imaging (MRI). This is also a very well known physical phenomenon that could be "simulated" using 3D software. Perhaps it's not a conventional 3D rendering procedure, because the intensities observed in an MRI scan are not responses to light, such as in conventional photography, but to magnetic resonance, as its name suggests.

Anyway, we could simulate various tissues and their responses to different machine configurations (intensity of the magnetic field, for instance) and render quite good MRI scans playing with tissue parameters. Then, we could produce a really large dataset of images with quite precise labelling at the pixel level, useful to train a recognition system for medical images. It could eventually work for xrays and other imaging modalities.

On the other hand, I wonder, if we can simulate that data, why can not we use the simulation function directly inside a learning algorithm? In other words, instead of generating the data to train a learning algorithm, the recognition system might also be ready to get that sort of simulation function as prior knowledge to make more effective predictions... does it make sense?

Bag of Features and Image Matching

I think bag of features is a good enough representation for image matching. Of course, it is not perfect, it still requires a lot of improvements. But it still captures many ideas that the computer vision community was working on a few years before it started to be popular.

For instance, consider the problem of image matching using SIFT features. The procedure goes like this:

1. Extract SIFT features from image A and B.
2. Build a list of descriptors for each image.
3. For each descriptor in image A, compute the distance to all other descriptors in image B.
4. Identify the minimum distance. If it is less than a threshold, count one match.
5. Repeat.

At the end of the procedure, we have the total number of matches between both images. As you can imagine, this is sort of expensive if we are supposed to compute the number of matches for a large set of images (not just between two images). There is when the bag-of-features (BoF) appears and introduces an intermediate layer to save some computations: the dictionary of visual patterns. Actually, instead of saving those computations, the BoF moves the effort to an off-line stage, when we can wait (the dictionary construction).

Later, when we are indexing images with the BoF, we pre-compute the number of matches between the descriptors of one image and a reference dictionary. That's the histogram of occurrences between two images. Afterwards, for a query image, we can estimate the total number of matches with respect to a previously indexed image, just by computing the histogram intersection between both histograms.

In other words, if image A shows the pattern "x" 5 times and image B shows the same pattern 3 times, guess what would be the number of common matches if we look directly from image to image without using a dictionary: 3 (because at least 3 of the patterns in A would match with those patterns in B, approximately, i.e., the minimum between 5 and 3). Sounds familiar? Of course, this is an approximation to the matching process described above using the histogram intersection metric. However, it sort of mimics what was previously done.

Notice that one important parameter in the direct matching process is the threshold to accept or reject a match. This is sort of relaxed in the BoF approach by using k-means to group similar patterns. I think it's relaxed because there is no rejection when using BoF (unless it would be sparse enough). So, here is the trick: the larger the number of patterns in the dictionary, the smaller the number of matches, and possibly the better the approximation.

I would argue that when the number of patterns goes to infinite, it is equivalent to have a matching process where the threshold is set to zero (a match requires exact descriptors). This sort of justifies the use of large dictionaries when using BoF. And it becomes even more important when we would like to use it in large scale setups, just because when we introduce more images, it is likely that more unseen visual patterns appear in the collection.