Robust feature matching for visual search

• US 9,036,925 B2
• Filed: 12/06/2011
• Issued: 05/19/2015
• Est. Priority Date: 04/14/2011
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Vaddadi, Sundeep, Hamsici, Onur C., Reznik, Yuriy, Hong, John H., Lee, Chong U.
• Primary Examiner(s): Carter, Aaron W
• Application Number:
  US13/312,335
• Publication Number:
  US 20120263388A1
• Time in Patent Office: 1,260 Days
• Field of Search: 382/225, 382/305, 707E17019-E17031
• US Class Current: 382/225
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/2413 based on distances to training or reference patterns

Abstract

Techniques are disclosed for performing robust feature matching for visual search. An apparatus comprising an interface and a feature matching unit may implement these techniques. The interface receives a query feature descriptor. The feature matching unit then computes a distance between a query feature descriptor and reference feature descriptors and determines a first group of the computed distances and a second group of the computed distances in accordance with a clustering algorithm, where this second group of computed distances comprises two or more of the computed distances. The feature matching unit then determines whether the query feature descriptor matches one of the reference feature descriptors associated with a smallest one of the computed distances based on the determined first group and second group of the computed distances.

Claims

1. A method for performing a visual search with a visual search device, the method comprising:

computing, with the visual search device, a distance between a query feature descriptor provided by way of a visual search query and each of a plurality of reference feature descriptors, wherein the visual search query initiates the visual search;

determining, with the visual search device, a first group of one or more of the computed distances and a second group of the computed distances in accordance with a clustering algorithm, wherein the first group of the computed distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are near to the query feature descriptor relative to the those of the computed distances determined to be in the second group of computed distances, and wherein the second group of the computed distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are far from the query feature descriptor relative to the those of the computed distances determined to be in the first group of the one or more of the computed distances;

determining, with the visual search device, whether the query feature descriptor matches one of the plurality of reference feature descriptors associated with a smallest one of the computed distances based on the determined first group of the computed distances and the second group of the computed distances;

determining a unique group of reference images to include reference images associated with those of the plurality of reference feature descriptors from which the computed distances determined to be in the first group were computed to a corresponding group of reference feature descriptors such that the set of reference images does not include duplicate reference images;

assigning a vote to each of the reference images determined to be in the unique group of reference images;

ordering the reference images based on the assigned votes; and

returning the ordered reference images in response to the visual search query.

2. The method of claim 1, wherein determining the first group of one or more of the computed distances and the second group of the computed distances includes determining the first group of the one or more of the computed distances and the second group of the computed distances in accordance with one or more of a k-means clustering algorithm, a Gaussian fitting algorithm and a graph cutting algorithm.

3. The method of claim 1, wherein determining whether the query feature descriptor matches one of the plurality of reference feature descriptors includes:

computing an average of the two or more of the computed distances determined to be in the first group to generate a first group distance average;

computing an average of the computed distances determined to be in the second group to generate a second group distance average;

dividing the first group distance average by the second group distance average to generate an average distance ratio measure;

comparing the average distance ratio measure to a threshold value; and

determining whether the query feature descriptor matches the one of the plurality of reference feature descriptors associated with the smallest one of the computed distances based on the comparison.

4. The method of claim 1, wherein assigning a vote to each of the reference images determined to be in the unique group of reference images includes one or more of:

assigning a constant vote to each of the reference images;

assigning a vote proportional to a distance ratio of the corresponding computed distance compared to the computed distance between the query feature descriptor and a closest one of the plurality of reference feature descriptors; and

assigning a vote proportional to a rank of the corresponding computed distance within the first group when the computed distances of the first group are ordered from smallest to largest.

5. The method of claim 1,

wherein the query feature descriptor comprises one of a plurality of query feature descriptors extracted from query image data in accordance with a visual search algorithm and provided by way of the visual search query, and

wherein the method further comprises:

for each of the plurality of query feature descriptors, computing a distance between a current one of the plurality of query feature descriptors and each of the plurality of reference feature descriptors to generate a computed plurality of distances;

for each of the plurality of distances, determining the first group of the computed plurality of distances and the second group of the computed plurality of distances in accordance with the clustering algorithm, wherein the first group of the computed plurality of distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are near to the query feature descriptor relative to the those of the computed plurality of distances determined to be in the second group of the computed plurality of distances, and wherein the second group of the computed plurality of distances includes those of the computed plurality of distances that indicate the associated one of the plurality of reference feature descriptors are far from the current one of the plurality of query feature descriptors relative to the those of the computed plurality of distances determined to be in the first group of computed plurality of distances; and

determining, with the visual search device, whether each of the plurality of query feature descriptor matches one of the plurality of reference feature descriptors associated with a smallest one of the computed plurality of distances based on the determined first group of the computed plurality of distances and the second group of the computed plurality of distances.

6. The method of claim 5, further comprising:

determining, for each of the plurality of query feature descriptors, a unique group of reference images to include reference images associated with those of the plurality of reference feature descriptors from which the computed plurality of distances determined to be in the first group were computed to a corresponding group of reference feature descriptors such that the set of reference images does not include duplicate reference images;

assigning a vote to each of the reference images determined to be in the unique group of reference images determined for each of the plurality of query feature descriptors;

after assigning the votes with respect to each of the plurality of query feature descriptors, ordering the reference images based on the assigned votes; and

returning the ordered reference images in response to the visual search query.

7. The method of claim 1, wherein the query feature descriptor is extracted from a query image in accordance with a local feature-based visual search algorithm.

8. The method of claim 7, wherein the local feature-based visual search algorithm comprises a scale invariant feature transform (SIFT) algorithm.

9. The method of claim 1, further comprising:

receiving the query feature descriptor as a compressed query feature descriptor via an interface of the visual search device from a client device; and

reconstructing the query feature descriptor from the compressed query feature descriptor with the visual search device.

10. An apparatus for performing a visual search, the apparatus comprising:

means for computing a distance between a query feature descriptor provided by way of a visual search query and each of a plurality of reference feature descriptors, wherein the visual search query initiates the visual search;

means for determining a first group of one or more of the computed distances and a second group of the computed distances in accordance with a clustering algorithm, wherein the first group of the computed distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are near to the query feature descriptor relative to the those of the computed distances determined to be in the second group of computed distances, and wherein the second group of the computed distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are far from the query feature descriptor relative to the those of the computed distances determined to be in the first group of the one or more of the computed distances;

means for determining whether the query feature descriptor matches one of the plurality of reference feature descriptors associated with a smallest one of the computed distances based on the determined first group of the computed distances and the second group of the computed distances;

means for determining a unique group of reference images to include reference images associated with those of the plurality of reference feature descriptors from which the computed distances determined to be in the first group were computed to a corresponding group of reference feature descriptors such that the set of reference images does not include duplicate reference images;

means for assigning a vote to each of the reference images determined to be in the unique group of reference images;

means for ordering the reference images based on the assigned votes; and

means for returning the ordered reference images in response to the visual search query.

11. The apparatus of claim 10, further comprising means for determining the first group of the one or more of the computed distances and the second group of the computed distances in accordance with one or more of a k-means clustering algorithm, a Gaussian fitting algorithm and a graph cutting algorithm.

12. The apparatus of claim 10, further comprising:

means for computing an average of the two or more of the computed distances determined to be in the first group to generate a first group distance average;

means for computing an average of the computed distances determined to be in the second group to generate a second group distance average;

means for dividing the first group distance average by the second group distance average to generate an average distance ratio measure;

means for comparing the average distance ratio measure to a threshold value; and

means for determining whether the query feature descriptor matches the one of the plurality of reference feature descriptors associated with the smallest one of the computed distances based on the comparison.

13. The apparatus of claim 10, further comprising one or more of:

means for assigning a constant vote to each of the reference images;

means for assigning a vote proportional to a distance ratio of the corresponding computed distance compared to the computed distance between the query feature descriptor and a closest one of the plurality of reference feature descriptors; and

means for assigning a vote proportional to a rank of the corresponding computed distance within the first group when the computed distances of the first group are ordered from smallest to largest.

14. The apparatus of claim 10,

wherein the query feature descriptor comprises one of a plurality of query feature descriptors extracted from query image data in accordance with a visual search algorithm and provided by way of the visual search query, and

wherein the apparatus further comprises:

means for computing, for each of the plurality of distances, a distance between a current one of the plurality of query feature descriptors and each of the plurality of reference feature descriptors to generate a computed plurality of distances;

means for determining, for each of the plurality of distances, the first group of the computed plurality of distances and the second group of the computed plurality of distances in accordance with the clustering algorithm, wherein the first group of the computed plurality of distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are near to the query feature descriptor relative to the those of the computed plurality of distances determined to be in the second group of the computed plurality of distances, and wherein the second group of the computed plurality of distances includes those of the computed plurality of distances that indicate the associated one of the plurality of reference feature descriptors are far from the current one of the plurality of query feature descriptors relative to the those of the computed plurality of distances determined to be in the first group of computed plurality of distances; and

means for determining whether each of the plurality of query feature descriptor matches one of the plurality of reference feature descriptors associated with a smallest one of the computed plurality of distances based on the determined first group of the computed plurality of distances and the second group of the computed plurality of distances.

15. The apparatus of claim 14, further comprising:

means for determining, for each of the plurality of query feature descriptors, a unique group of reference images to include reference images associated with those of the plurality of reference feature descriptors from which the computed plurality of distances determined to be in the first group were computed to a corresponding group of reference feature descriptors such that the set of reference images does not include duplicate reference images;

means for assigning a vote to each of the reference images determined to be in the unique group of reference images determined for each of the plurality of query feature descriptors;

after assigning the votes with respect to each of the plurality of query feature descriptors, means for ordering the reference images based on the assigned votes; and

means for returning the ordered reference images in response to the visual search query.

16. The apparatus of claim 10, wherein the query feature descriptor is extracted from a query image in accordance with a local feature-based visual search algorithm.

17. The apparatus of claim 16, wherein the local feature-based visual search algorithm comprises a scale invariant feature transform (SIFT) algorithm.

18. The apparatus of claim 10, further comprising:

means for receiving the query feature descriptor as a compressed query feature descriptor via an interface of a visual search device from a client device; and

means for reconstructing the query feature descriptor from the compressed query feature descriptor with the visual search device.

19. An apparatus configured to perform a visual search, the apparatus comprising:

an interface configured to receive a query feature descriptor;

a feature matching unit configured to;

compute a distance between the query feature descriptor provided by way of a visual search query and each of a plurality of reference feature descriptors, wherein the visual search query initiates the visual search, and configured to determine a first group of one or more of the computed distances and a second group of the computed distances in accordance with a clustering algorithm, wherein the first group of the computed distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are near to the query feature descriptor relative to the those of the computed distances determined to be in the second group of computed distances, and wherein the second group of the computed distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are far from the query feature descriptor relative to the those of the computed distances determined to be in the first group of the one or more of the computed distances and wherein the feature matching unit is further configured to determine whether the query feature descriptor matches one of the plurality of reference feature descriptors associated with a smallest one of the computed distances based on the determined first group of the computed distances and the second group of the computed distances;

determine a unique group of reference images to include reference images associated with those of the plurality of reference feature descriptors from which the computed distances determined to be in the first group were computed to a corresponding group of reference feature descriptors such that the set of reference images does not include duplicate reference images;

assign a vote to each of the reference images determined to be in the unique group of reference images;

order the reference images based on the assigned votes; and

return the ordered reference images in response to the visual search query.

20. The apparatus of claim 19, wherein the feature matching unit is configured to determine the first group of the one or more of the computed distances and the second group of the computed distances in accordance with one or more of a k-means clustering algorithm, a Gaussian fitting algorithm and a graph cutting algorithm.

21. The apparatus of claim 19, wherein the feature matching unit is further configured to compute an average of the two or more of the computed distances determined to be in the first group to generate a first group distance average, to compute an average of the computed distances determined to be in the second group to generate a second group distance average, to divide the first group distance average by the second group distance average to generate an average distance ratio measure, and to compare the average distance ratio measure to a threshold value and determine whether the query feature descriptor matches the one of the plurality of reference feature descriptors associated with the smallest one of the computed distances based on the comparison.

22. The apparatus of claim 19, wherein the feature matching unit is configured to assign the vote by one or more of assigning a constant vote to each of the reference images, assigning a vote proportional to a distance ratio of the corresponding computed distance compared to the computed distance between the query feature descriptor and a closest one of the plurality of reference feature descriptors and assigning a vote proportional to a rank of the corresponding computed distance within the first group when the computed distances of the first group are ordered from smallest to largest.

23. The apparatus of claim 19,

wherein the query feature descriptor comprises one of a plurality of query feature descriptors extracted from query image data in accordance with a visual search algorithm and provided by way of the visual search query, and

wherein the feature matching unit is further configured to:

for each of the plurality of query feature descriptors, compute a distance between a current one of the plurality of query feature descriptors and each of the plurality of reference feature descriptors to generate a computed plurality of distances;

for each of the plurality of distances, determine the first group of the computed plurality of distances and the second group of the computed plurality of distances in accordance with the clustering algorithm, wherein the first group of the computed plurality of distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are near to the query feature descriptor relative to the those of the computed plurality of distances determined to be in the second group of the computed plurality of distances, and wherein the second group of the computed plurality of distances includes those of the computed plurality of distances that indicate the associated one of the plurality of reference feature descriptors are far from the current one of the plurality of query feature descriptors relative to the those of the computed plurality of distances determined to be in the first group of computed plurality of distances; and

determine whether each of the plurality of query feature descriptor matches one of the plurality of reference feature descriptors associated with a smallest one of the computed plurality of distances based on the determined first group of the computed plurality of distances and the second group of the computed plurality of distances.

24. The apparatus of claim 23, wherein the feature matching unit is further configured to:

determines, for each of the plurality of query feature descriptors, a unique group of reference images to include reference images associated with those of the plurality of reference feature descriptors from which the computed plurality of distances determined to be in the first group were computed to a corresponding group of reference feature descriptors such that the set of reference images does not include duplicate reference images;

assign a vote to each of the reference images determined to be in the unique group of reference images determined for each of the plurality of query feature descriptors, after assigning the votes with respect to each of the plurality of query feature descriptors, orders the reference images based on the assigned votes; and

wherein the interface returns the ordered reference images in response to the visual search query.

25. The apparatus of claim 19, wherein the query feature descriptor is extracted from a query image in accordance with a local feature-based visual search algorithm.

26. The apparatus of claim 25, wherein the local feature-based visual search algorithm comprises a scale invariant feature transform (SIFT) algorithm.

27. The apparatus of claim 19,

wherein the interface is configured to receive the query feature descriptor as a compressed query feature descriptor from a client device, and

wherein the apparatus includes a feature reconstruction unit that is configured to reconstruct the query feature descriptor from the compressed query feature descriptor with a visual search device.

28. A non-transitory computer-readable medium comprising instruction that, when executed, cause one or more processors to:

compute a distance between a query feature descriptor provided by way of a visual search query and each of a plurality of reference feature descriptors, wherein the visual search query initiates a visual search;

determine a first group of one or more of the computed distances and a second group of the computed distances in accordance with a clustering algorithm, wherein the first group of the computed distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are near to the query feature descriptor relative to the those of the computed distances determined to be in the second group of computed distances, and wherein the second group of the computed distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are far from the query feature descriptor relative to the those of the computed distances determined to be in the first group of the one or more of the computed distances;

determine whether the query feature descriptor matches one of the plurality of reference feature descriptors associated with a smallest one of the computed distances based on the determined first group of the computed distances and the second group of the computed distances;

determine a unique group of reference images to include reference images associated with those of the plurality of reference feature descriptors from which the computed distances determined to be in the first group were computed to a corresponding group of reference feature descriptors such that the set of reference images does not include duplicate reference images;

assign a vote to each of the reference images determined to be in the unique group of reference images;

order the reference images based on the assigned votes; and

return the ordered reference images in response to the visual search query.

29. The non-transitory computer-readable medium of claim 28, further comprising instructions that cause, when executed, the one or more processors to determine the first group of the one or more of the computed distances and the second group of the computed distances in accordance with one or more of a k-means clustering algorithm, a Gaussian fitting algorithm and a graph cutting algorithm.

30. The non-transitory computer-readable medium of claim 28, further comprising instructions that cause, when executed, the one or more processors to:

compute an average of the two or more of the computed distances determined to be in the first group to generate a first group distance average;

compute an average of the computed distances determined to be in the second group to generate a second group distance average;

divide the first group distance average by the second group distance average to generate an average distance ratio measure;

compare the average distance ratio measure to a threshold value; and

determine whether the query feature descriptor matches the one of the plurality of reference feature descriptors associated with the smallest one of the computed distances based on the comparison.

31. The non-transitory computer-readable medium of claim 28, further comprising instructions that cause, when executed, the one or more processors to:

assign a constant vote to each of the reference images;

assign a vote proportional to a distance ratio of the corresponding computed distance compared to the computed distance between the query feature descriptor and a closest one of the plurality of reference feature descriptors; and

assign a vote proportional to a rank of the corresponding computed distance within the first group when the computed distances of the first group are ordered from smallest to largest.

32. The non-transitory computer-readable medium of claim 28,

wherein the query feature descriptor comprises one of a plurality of query feature descriptors extracted from query image data in accordance with a visual search algorithm and provided by way of the visual search query,

wherein the computer-readable medium further comprises instructions that cause, when executed, the one or more processors to:

for each of the plurality of query feature descriptors, compute a distance between a current one of the plurality of query feature descriptors and each of the plurality of reference feature descriptors to generate a computed plurality of distances;

for each of the plurality of distances, determine the first group of the computed plurality of distances and the second group of the computed plurality of distances in accordance with the clustering algorithm, wherein the first group of the computed plurality of distances includes those of the computed distances that indicate the associated one of the plurality of reference feature descriptors are near to the query feature descriptor relative to the those of the computed plurality of distances determined to be in the second group of the computed plurality of distances, and wherein the second group of the computed plurality of distances includes those of the computed plurality of distances that indicate the associated one of the plurality of reference feature descriptors are far from the current one of the plurality of query feature descriptors relative to the those of the computed plurality of distances determined to be in the first group of computed plurality of distances; and

determine whether each of the plurality of query feature descriptor matches one of the plurality of reference feature descriptors associated with a smallest one of the computed plurality of distances based on the determined first group of the computed plurality of distances and the second group of the computed plurality of distances.

33. The non-transitory computer-readable medium of claim 32, further comprising instructions that cause, when executed, the one or more processors to:

determine, for each of the plurality of query feature descriptors, a unique group of reference images to include reference images associated with those of the plurality of reference feature descriptors from which the computed plurality of distances determined to be in the first group were computed to a corresponding group of reference feature descriptors such that the set of reference images does not include duplicate reference images;

assign a vote to each of the reference images determined to be in the unique group of reference images determined for each of the plurality of query feature descriptors;

after assigning the votes with respect to each of the plurality of query feature descriptors, order the reference images based on the assigned votes; and

return the ordered reference images in response to the visual search query.

34. The non-transitory computer-readable medium of claim 28, wherein the query feature descriptor is extracted from a query image in accordance with a local feature-based visual search algorithm.

35. The non-transitory computer-readable medium of claim 34, wherein the local feature-based visual search algorithm comprises a scale invariant feature transform (SIFT) algorithm.

36. The non-transitory computer-readable medium of claim 28, further comprising instructions that cause, when executed, the one or more processors to:

receive the query feature descriptor as a compressed query feature descriptor via an interface of a visual search device from a client device; and

reconstruct the query feature descriptor from the compressed query feature descriptor with the visual search device.

37. A system comprising:

an input to receive information received from one or more client devices, wherein the information comprises a query feature descriptor to initiate a visual search;

a database including information indicative of a plurality of reference query descriptors; and

a visual search server device configured to perform the visual search, the visual search server device comprising;

an interface to receive the query feature descriptor; and

a feature matching unit configured to;

compute a distance between the query feature descriptor and each of the plurality of reference query descriptors;

determine a first group of one or more of the computed distances and a second group of the computed distances in accordance with a clustering algorithm, wherein the first group of the computed distances includes those of the computed distances that indicate the associated one of the plurality of reference query descriptors are near to the query feature descriptor relative to the those of the computed distances determined to be in the second group of computed distances, and wherein the second group of the computed distances includes those of the computed distances that indicate the associated one of the plurality of reference query descriptors are far from the query feature descriptor relative to the those of the computed distances determined to be in the first group of the one or more of the computed distances;

determine whether the query feature descriptor matches one of the plurality of reference query descriptors associated with a smallest one of the computed distances based on the determined first group of the computed distances and the second group of the computed distances;

determine a unique group of reference images to include reference images associated with those of the plurality of reference feature descriptors from which the computed distances determined to be in the first group were computed to a corresponding group of reference feature descriptors such that the set of reference images does not include duplicate reference images;

assign a vote to each of the reference images determined to be in the unique group of reference images;

order the reference images based on the assigned votes; and

return the ordered reference images in response to the visual search query.