Efficient local feature descriptor filtering

Patent metadata

Field	Value
Publication number	US-9430718-B1
Application number	US-201514617373-A
Country	US
Kind code	B1
Filing date	Feb 9, 2015
Priority date	Feb 9, 2015
Publication date	Aug 30, 2016
Grant date	Aug 30, 2016

Abstract

The present disclosure generally relates to methods and computer program products for searching for a similar image among a plurality of stored images, and in particular to a method and computer program product used in a content based image retrieval system where roughly similar images are clustered and feature vectors for the clustered images are filtered based on a matching frequency for the feature vectors among the images in the cluster.

First claim

The invention claimed is:

1. A method for searching for a similar image among a plurality of stored images, comprising the steps of:
for each stored image, calculating only one feature vector representing the content of the stored image,
calculating distance measures between each stored image of the plurality of stored images by using the one feature vector calculated for each image,
clustering the plurality of stored images into one or more clusters of stored images based on the calculated distance measures, wherein each cluster comprises one or more stored images,
for each cluster comprising a plurality of stored images,
for each stored image in the cluster, calculating a plurality of feature vectors, each representing the content of the stored image,
performing a matching operation between at least some of the plurality of feature vectors for all of the stored images in the cluster, and
based on a result of the matching operation, filtering feature vectors which are matched between at least a threshold number of the stored images, and
storing the filtered feature vectors,

retrieving an image for which a similar image should be found,
calculating a plurality of additional feature vectors for the retrieved image,
finding a similar image among the plurality of stored images by using the stored filtered feature vectors for at least one of the one or more clusters, and the additional feature vectors.

2. The method according to claim 1 , wherein the step of storing the filtered feature vectors comprises:
storing the filtered feature vectors with a reference to the cluster.

3. The method according to claim 2 , wherein the step of finding a similar image among the plurality of stored images comprises:
finding a matching cluster by comparing the additional feature vectors with the filtered feature vectors for each cluster, and
finding a similar image among the plurality of stored images in the matching cluster.

4. The method according to claim 1 , wherein the step of storing the filtered feature vectors comprises:
for each stored image in plurality of stored images, storing the filtered feature vectors corresponding to the content of the stored image with a reference to the stored image.

5. The method according to claim 1 , wherein the step of storing the filtered feature vectors comprises:
storing the filtered feature vectors with a reference to the cluster, and
for each stored image in plurality of stored images, storing the filtered feature vectors corresponding to the content of the stored image with a reference to the stored image.
wherein the step of finding a similar image among the plurality of stored images comprises:
finding a matching cluster by comparing the additional feature vectors with the filtered feature vectors for each cluster, and
finding a similar image among the plurality of stored images in the matching cluster by for at least some images in the matching cluster, comparing the additional feature vectors with the filtered feature vectors corresponding to the content of the stored image.

6. The method according to claim 1 , further comprising the step of:
for each cluster comprising a plurality of stored images,
ordering the plurality of stored images in a tree data structure based on the calculated distance measures, wherein each image of the plurality of images corresponds to a node in the tree data structure, and wherein one image of the plurality of images corresponds to a root node in the tree data structure.

7. The method according to claim 1 , further comprising the steps of:
marking a cluster as uninteresting,
determining if the retrieved image is similar to an image in a cluster marked as uninteresting, and if this is true,
deleting the retrieved image.

8. The method according to claim 1 , further comprising the steps of:
marking a cluster as interesting,
determining if the retrieved image is similar to an image in a cluster marked as interesting, and if this is true,
storing the retrieved image.

9. The method according to claim 8 , wherein the step of storing the retrieved image comprises storing the retrieved image in a cloud storage.

10. The method according to claim 1 , wherein the matching operation comprises using a random sample consensus (RANSAC) algorithm.

11. The method according to claim 1 , wherein the plurality of feature vectors are calculated by using a Scale-invariant feature transform (SIFT) algorithm or a Speeded Up Robust Features (SURF) algorithm.

12. The method according to claim 1 , wherein the distance measures calculated between each stored image of the plurality of stored images by using the one feature vector calculated for each image is calculated by using an earth mover's distance (EMD) algorithm.

13. The method according to claim 1 , wherein in the step of for each stored image, calculating only one feature vector representing the content of the stored image, the only one feature vector is calculated based on an interpolated version of the stored image.

14. A computer program product comprising a non-transitory computer-readable storage medium storing instructions adapted to carry out the method of claim 1 when executed by an instruction processing device.

Assignees

• Sony Corp

Inventors

• Engström Jimmy

Classifications

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title

• G06F16/5838 Primary

  using colour · CPC title

• G06F18/23

  Clustering techniques · CPC title

• G06K9/6218

  Physics · mapped topic

• G06F17/30256

  Physics · mapped topic