Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.
Sign up to join this community
How are the descriptors in the BRIEF algorithm matched to each other?
How is the template image found in the another image? How do we compare the descriptors? I have read that article but didn't understand how they have done it.
They wrote that they compared descriptors by using Hamming distance, but how is invariance to changes in illumination, size, etc. achieved?
First of all, there's no such thing as 'template' in this paper - the word 'template(s)' has a different meaning in Computer Vision.
The method used in this paper is relatively straight-forward. Let me break it down for you. There are three important things that you need to do when doing tasks such as object recognition, image matching, image stitching, and similar others, using Local Features
The first important thing is Detection; in this step you want to detect points-of-interest or keypoints, and what that means is that you want to choose local points (basically small patches) that you think are interesting in the image, there are many ways to do that; this paper doesn't contribute in this area. However, it seems that they use SURF feature detector and CenSurE keypoints (you can look them up if you want to know more about them, I won't talk about this step except that they use features such as gradients and so, which means that if you have a photo, it's unlikely that a point in the middle of the sky would be chosen as an interest point, that's because the pixels around that point are all same intensities, things that are 'busy' tend to be chosen as interest points (e.g. table/building edges/corners)).
After detection is done, Feature Description follows. You know the interesting points in the image and now you want to describe them (basically you want to describe the points/patch around the interesting points). SIFT is one popular feature descriptor. In this paper, they come up with a new one, called BRIEF. BRIEF is based on comparisons, so let's say we have a patch (50 pixels by 50 pixels), we choose two points and compare the intensities of the two points, if the first point is larger than the second point, we assign the value '1', else '0', we do that for a number of pairs and we end up with a string of boolean values. Now the big question is 'how do you pick the pair of points?', in the paper they explained 5 ways, relatively similar, I will describe the first one. What you do is you uniformly (equal probability) choose a point from -S/2 to S/2, in our example we said that the patch size is 50, so we choose a point between -25 to 25. Assuming that the 0,0 coordinate is located at the center of the patch. So here's an example;
We want to select the first pair, each point consists of (X,Y) coordinates so we uniformly select the X-coordinate of the first point, then the Y-coordinate of the first point, let's assume it's (10,-1), now the second point; we uniformly select the X-coordinate for the second point, and the Y-coordinate for the second point, let's assume it's (-2,20), now we get the intensity values for each point and see which one has the larger intensity values - if first is larger we assign the first boolean value to be '1', if not, we assign '0'. We do that for many pairs, and we end up with a vector of boolean values.
*Very important point: I assume for this to work, you will have to specify a seed value before the random generator. What that means is that you want to choose the same values for each patch - this is super important because when you compare/match patches, the whole system will break down if they're not chosen the exact same way. - hopefully this will make sense when you read the matching step.
So, we do that for each interest point that was detected by the detector. For each interest point, we will get a vector of boolean values.
Now to match two images (third step; matching), we do the exact same thing for the other image, we detect, then describe using the BRIEF. For example let's say we have 10 interest points in each image (this can always work if we get the 10 most interesting points in each image), we use BRIEF to describe each patch using for example 50 pairs, so each image will be described by 10 vectors of 50 boolean values.
To compare the two images, we find the nearest neighbor of each vector from the first image to each other vector from the second image. We use Hamming distance which is pretty fast, example of hamming distance
hammingDistance((0, 1, 1), (0, 0, 0)) = 2
hammingDistance((0, 1, 1), (0, 1, 1)) = 0
hammingDistance((0, 1, 1), (1, 0, 0)) = 3
hammingDistance((0, 1, 1), (1, 1, 1)) = 1
Basically how many wrong correspondences
Hope that helps
