Fast interest point extraction for augmented reality
View Patent ↗The subject technology provides embodiments for performing fast corner detection in a given image for augmented reality applications. Embodiments disclose a high-speed test that examines intensities of pairs of pixels around a candidate center pixel. In one example, the examined pairs are comprised of pixels that are diametrically opposite ends of a circle formed with the candidate center pixel. Further, a pyramid of images including four rings of surrounding pixels is generated. An orientation of the pixels from the four rings are determined and a vector of discrete values of the pixels are provided. Next, a forest of trees are generated for the vector of discrete values corresponding to a descriptor for a first image. For a second image including a set of descriptors, approximate nearest neighbors are determined from the forest of tree representing closest matching descriptors from the first image.
1. A computer-implemented method, the method comprising:
identifying a candidate corner feature in a first image, the candidate corner feature including a set of pixels from the first image;
determining a center pixel from the set of pixels;
selecting, from the set of pixels, a subset of pixels, each pixel from the subset of pixels being at a respective distance from the center pixel, wherein the subset of pixels comprises a ring shape that surrounds the center pixel;
downscaling the set of pixels from the first image, the downscaled set of pixels representing a second layer of a pyramid and the set of pixels representing a bottom layer of the pyramid;
determining a first derivative value based at least in part on of a weighted sum of intensities of respective pixels from a right side of the downscaled set of pixels and intensities of respective pixels from the left side of the downscaled set of pixels;
determining a second derivative value based at least in part on of a second weighted sum of intensities of respective pixels from an upper side of the downscaled set of pixels and intensities of respective pixels from a bottom side of the downscaled set of pixels;
determining an orientation angle using at least an arctangent function on the first and second derivative values;
shifting values of a subset of pixels from the downscaled set of pixels based at least in part on the orientation angle, the subset of pixels comprising a ring that surrounds a respective center pixel of the downscaled set of pixels; and
confirming a corner feature of the first image based at least in part on:
determining that intensities of at least a pair of pixels are not within a threshold value of the intensity of the center pixel; and
determining that an intensity of a first pixel from the at least the pair of pixels is unequal to an intensity of a second pixel from the at least the pair of pixels; and
providing the confirmed corner feature to at least one object recognition process.
2. The computer-implemented method of claim 1 , further comprising;
downscaling the set of pixels from the first image, the downscaled set of pixels representing a second layer of a pyramid and the set of pixels representing a bottom layer of the pyramid, the second layer of the pyramid having a greater radius than the bottom layer of the pyramid;
generating, using at least in part the set of pixels from the first image, a plurality of rings of pixels, each ring of pixels representing a successive downscaled image of the set of pixels and a successive layer of a pyramid; and
generating a vector of values based at least in part on respective intensity values for each pixel from the plurality of rings of pixels.
3. The computer-implemented method of claim 2 , further comprising:
generating a forest of tree data structures for a set of descriptor values from the first image based on the vector of values; and
determining, for set of descriptor values of a second image, a set of nearest neighbors from the first image based at least in part on the forest of tree data structures.
4. A system comprising:
at least one processor; and
a memory device including instructions that, when executed by the at least one processor, cause the at least one processor to:
identify a candidate corner feature in a first image, the candidate corner feature including a set of pixels from the first image;
determine a center pixel from the set of pixels;
select, from the set of pixels, a subset of pixels, each pixel from the subset of pixels being at a respective distance from the center pixel;
determine a corner feature of the first image based at least in part on comparing an intensity of the center pixel to intensities of at least a pair of pixels from the subset of pixels;
downscale the set of pixels from the first image, the downscaled set of pixels representing an outer layer of a pyramid and the set of pixels representing an inner layer of the pyramid, the outer layer having a greater radius than the inner layer;
determine a first derivative value based at least in part on of a weighted sum of intensities of respective pixels from a right side of the downscaled set of pixels and intensities of respective pixels from the left side of the downscaled set of pixels;
determine a second derivative value based at least in part on of a second weighted sum of intensities of respective pixels from an upper side of the downscaled set of pixels and intensities of respective pixels from a bottom side of the downscaled set of pixels;
determine an orientation angle using at least an arctangent function on the first and second derivative values; and
shift values of a subset of pixels from the downscaled set of pixels based at least in part on the orientation angle, the subset of pixels comprising a ring that surrounds a respective center pixel of the downscaled set of pixels.
5. The system of claim 4 , wherein the subset of pixels includes sixteen pixels, the sixteen pixels comprising a ring shape that surrounds the center pixel.
6. The system of claim 4 , wherein to determine the corner feature of the first image further causes the at least one processor to:
determine that an intensity of the at least the pair of pixels is not within a threshold value of the intensity of the center pixel.
7. The system of claim 6 , wherein the instructions further cause the at least one processor to:
select a second pair of pixels from the subset of pixels, the second pair of pixels being different than the at least the pair of pixels; and
determine that intensities of the second pair of pixels are not within the threshold value of the intensity of the center pixel.
8. The system of claim 6 , wherein the instructions further cause the at least one processor to:
determine that an intensity of a first pixel from the at least the pair of pixels is unequal to an intensity of a second pixel from the at least the pair of pixels.
9. The system of claim 4 , wherein the instructions further cause the at least one processor to:
downscale the set of pixels from the first image, the downscaled set of pixels representing a second layer of a pyramid and the set of pixels representing a bottom layer of the pyramid, the second layer of the pyramid having a greater radius than the bottom layer of the pyramid;
generate, using at least in part the set of pixels from the first image, a plurality of rings of pixels, each ring of pixels representing a successive downscaled image of the set of pixels and a successive layer of a pyramid; and
generate a vector of values based at least in part on respective intensity values for each pixel from the plurality of rings of pixels.
10. The system of claim 9 , wherein the instructions further cause the at least one processor to:
generate a forest of tree data structures for a set of descriptor values from the first image based on the vector of values.
11. The system of claim 10 , wherein the instructions further cause the at least one processor to:
determine, for set of descriptor values of a second image, a set of nearest neighbors from the first image based at least in part on the forest of tree data structures.
12. A non-transitory computer-readable medium including instructions stored therein that, when executed by at least one computing device, cause the at least one computing device to:
identify a candidate corner feature in a first image, the candidate corner feature including a set of pixels from the first image;
determine a center pixel from the set of pixels;
select, from the set of pixels, a subset of pixels, each pixels from the subset of pixels being at a respective distance from the center pixel;
determine a corner feature of the first image based at least in part on comparing an intensity of the center pixel to intensities of at least a pair of pixels from the subset of pixels;
downscale the set of pixels from the first image, the downscaled set of pixels representing an outer layer of a pyramid and the set of pixels representing a bottom layer of the pyramid, the outer layer having a greater radius than the bottom layer of the pyramid;
determine a first derivative value based at least in part on of a weighted sum of intensities of respective pixels from a right side of the downscaled set of pixels and intensities of respective pixels from the left side of the downscaled set of pixels;
determine a second derivative value based at least in part on of a second weighted sum of intensities of respective pixels from an upper side of the downscaled set of pixels and intensities of respective pixels from a bottom side of the downscaled set of pixels;
determine an orientation angle using at least an arctangent function on the first and second derivative values; and
shift values of a subset of pixels from the downscaled set of pixels based at least in part on the orientation angle, the subset of pixels comprising a ring that surrounds a respective center pixel of the downscaled set of pixels.
13. The non-transitory computer-readable medium of claim 12 , wherein to determine the corner feature of the first image further causes the at least one computing device to:
determine that intensities of the at least the pair of pixels are not within a threshold value of the intensity of the center pixel.
14. The non-transitory computer-readable medium of claim 13 , wherein the instructions further cause the at least one computing device to:
select a second pair of pixels from the subset of pixels, the second pair of pixels being different than the at least the pair of pixels; and
determine that intensities of the second pair of pixels are not within the threshold value of the intensity of the center pixel.
15. The non-transitory computer-readable medium of claim 12 , wherein the instructions further cause the at least one computing device to:
downscale the set of pixels from the first image, the downscaled set of pixels representing a second layer of a pyramid and the set of pixels representing a bottom layer of the pyramid, the second layer having a greater radius than the bottom layer of the pyramid;
generate, using at least in part the set of pixels from the first image, a plurality of rings of pixels, each ring of pixels representing a successive downscaled image of the set of pixels and a successive layer of a pyramid;
generate a vector of values based at least in part on respective intensity values for each pixel from the plurality of rings of pixels; and
generate a forest of tree data structures for a set of descriptor values from the first image based on the vector of values.
16. The non-transitory computer-readable medium of claim 15 , wherein the instructions further cause the at least one computing device to:
determine, for set of descriptor values of a second image, a set of nearest neighbors from the first image based at least in part on the forest of tree data structures.
17. The non-transitory computer-readable medium of claim 15 , wherein the intensity values comprise an 8-bit value within a range of 0 to 255.
18. The system of claim 9 , wherein the intensity values comprise an 8-bit value within a range of 0 to 255.
19. The non-transitory computer-readable medium of claim 12 , wherein the subset of pixels includes sixteen pixels, the sixteen pixels comprising a ring shape that surrounds the center pixel.
20. The non-transitory computer-readable medium of claim 13 , wherein the instructions further cause the at least one computing device to:
determine that an intensity of a first pixel from the at least the pair of pixels is unequal to an intensity of a second pixel from the at least the pair of pixels.