5 – 04 Brief V4

The second part of the orb algorithm is to take the key points found by the first algorithm and turn those into feature vectors that together can represent an object. To create feature vectors, orb uses the BRIEF algorithm. BRIEF stands for binary robust independent elementary features, and its purpose is to create binary feature vectors from a set of key points. As we saw in the introduction video, a binary feature vector, also known as a binary descriptor, is just a feature vector that contains only ones and zeros. In BRIEF, each key point is described by a binary feature vector that has a 128-512 bits string that only contains ones and zeros. Just as a reminder, bit is short for a binary digit; and one bit can hold only a single binary value, either a one or a zero, and a bit string is just a group of bits. Here we see some examples of bit strings: the first is a one bit string therefore it only holds 1 bit, the second is a two bit string therefore it can hold 2 binary digits. In this case it holds a zero and one. Similarly, the third is a three bit string and so it can hold 3 bits and so on. Computers run on binary or machine code, and so the great advantage of using binary feature vectors is that they can be stored very efficiently in memory and they can be computed quickly. These properties not only make BRIEF very fast, which is crucial for real time applications, but they also allow BRIEF to run on devices with very limited computational resources, such as your smartphone. So, how does BRIEF create these binary descriptors for each point? The BRIEF algorithm starts by smoothing a given image with a Gaussian kernel in order to prevent the descriptor from being too sensitive to high frequency noise. Next, given a key point like the one here and the cat’s paw, BRIEF selects a random pair of pixels inside a defined neighborhood around that key point. The neighborhood around the key point is known as a patch, which is a square with some pixel width and height. The first pixel in the random pair, shown here is a blue square, is drawn from a Gaussian distribution centered around the key point and with a standard deviation or a spread of Sigma. The second pixel in the random pair, shown here as a yellow square, is drawn from a Gaussian distribution centered around that first pixel and with a standard deviation of Sigma over 2. It’s been shown empirically that this choice of Gaussians improves the feature matching rates. BRIEF then starts constructing the binary descriptor for the key point by comparing the brightness of the two pixels as follows: If the first pixel is brighter than the second, it assigns the value of one to the corresponding bit in the descriptor. Otherwise it assigns the value of zero. In this example we see here, the second pixel is brighter than the first pixel, so we assign a value of zero to the first bit of our feature vector. The first bit of the feature vector corresponds to the first random pair of points for this key point. Now, for the same key point, BRIEF selects a new random pair of pixels, compares their brightness and assigns one or zero to the next bit and the feature vector. In our example, we see that now the first pixel is brighter than the second, therefore we assign a value of one to the second bit in our feature vector. For a 256 bit vector, BRIEF then repeats this process for the same key point 256 times before moving onto the next key point. The results of the 256 pixel brightness comparisons are then put into the binary feature vector for that one key point. BRIEF creates a vector like this for each key point in an image. Now, that you know how BRIEF constructs feature vectors for the key points found by first, next, we’ll see how orb uses these to create vectors that are robust in the face of image rotation, scale and noise.

%d 블로거가 이것을 좋아합니다: