Approximate cross-check for real-time feature matching

1. A method of feature matching comprising the steps of:

determining a set of correspondences between a set of reference feature points for a first image and a set of target feature points for a second image using a processor to compute a descriptor matching function for each pair of reference and target feature points; and

reducing the set of correspondences using said processor to perform an approximate cross-check to obtain a set of valid correspondences based upon said descriptor matching function computed for each pair of feature points and continuously update the set of valid correspondences found after the approximate cross-check.

2. The method according to claim 1 , wherein the determining and reducing steps are performed concurrently.

3. The method according to claim 1 , wherein the determining and reducing steps generate said set of valid correspondences using a single pass through said set of reference feature points.

4. The method according to claim 1 , wherein said feature matching is performed with said approximate cross-check in real time.

5. The method according to claim 1 , wherein the set of valid correspondences found after the approximate cross-check are identified using a pair of arrays and the processor continuously updates the pair of arrays identifying the valid correspondences.

6. The method according to claim 1 , wherein said descriptor matching function compares two corresponding descriptors of each pair of reference and target feature points.

7. The method according to claim 1 , wherein:

for binary descriptors said descriptor matching function computes a hamming distance; and

for real descriptors said descriptor matching function computes at least one of an L1 norm, an L2 norm, or a combination thereof.

8. The method according to claim 1 , wherein said first image and said second image comprise at least one of (i) frames in a video sequence and (ii) pictures of a scene taken at different points in time.

9. The method according to claim 1 , further comprising:

generating at least one of an estimate of ego-motion of a computer vision platform and a motion model of observed objects in a scene.

10. An apparatus comprising:

a memory interface configured to perform read and write operations on a memory; and

a processor configured to (i) determine a set of correspondences between a set of reference feature points for a first image and a set of target feature points for a second image by computing a descriptor matching function for each pair of reference and target feature points, and (ii) reduce the set of correspondences by performing an approximated cross-check scheme to obtain a set of valid correspondences based upon said descriptor matching function computed for each pair of feature points and continuously updating the set of valid correspondences found after the approximate cross-check.

11. The apparatus according to claim 10 , wherein said processor determines and reduces the set of correspondences concurrently.

12. The apparatus according to claim 10 , wherein said processor generates said set of valid correspondences using a single pass through said set of reference feature points.

13. The apparatus according to claim 10 , wherein said processor is further configured to continuously update a pair of arrays identifying the valid correspondences found after the approximate cross-check.

14. The apparatus according to claim 10 , wherein said descriptor matching function compares two corresponding descriptors of each pair of reference and target feature points.

15. The apparatus according to claim 10 , wherein:

for binary descriptors said descriptor matching function computes a hamming distance; and

for real descriptors said descriptor matching function computes at least one of an L1 norm, an L2 norm, or a combination thereof.

16. The apparatus according to claim 15 , wherein said descriptor matching function for binary descriptors is computed using a circuit configured to generate a vector through a bitwise exclusive-OR of two corresponding descriptors of each pair of reference and target feature points and sum across the vector.

17. The apparatus according to claim 10 , wherein said first image and said second image are at least one of frames in a video sequence or pictures of a scene taken at different points in time.

18. The apparatus according to claim 10 , wherein said memory interface and said processor are implemented on a single integrated circuit.

19. The apparatus according to claim 10 , wherein said memory interface and said processor are part of a system on chip.

20. The apparatus according to claim 10 , wherein said memory interface and said processor are part of a processor chip of digital camera.