Image search device, image search method, program, and computer-readable storage medium

1. An image search device, comprising:

a processor; and

a memory device that stores a plurality of instructions, which when executed by the processor, causes the processor to:

obtain a plurality of query image feature vectors, wherein each of said plurality of query image feature vectors indicate a local feature of a query image;

select, for each of the plurality of query image feature vectors, search image feature vectors which indicate local features of each of a plurality of search images, and wherein said search image feature vectors are stored in a storage unit in advance for each of the plurality of search images;

generate a score indicating a degree of similarity between each of the plurality of search images and the query image based on the search image feature vectors selected relative to the plurality of query image feature vectors; and

select an image from the plurality of search images based on the score generated for the search image,

wherein in the selection of the search image feature vectors, an already-selected image list is initialized for each of the query image feature vectors, one or more search image feature vectors are selected for the query image feature vectors, not more than one search image feature vector is selected from the one or more selected search image feature vectors, the not more than one selected search image feature vector has not been extracted from an image included in the already-selected image list, and the image from which the not more than one selected search image feature vector has been extracted is added to the already-selected image list.

2. The image search device according to claim 1 , wherein the plurality of instructions further cause the processor to:

select a cluster corresponding to each of the plurality of query image feature vectors from a plurality of clusters into which a plurality of search image feature vectors indicating features of the plurality of search images are classified,

wherein in the selection of the search image feature vector, the search image feature vector is selected, for each of the plurality of query image feature vectors, from the plurality of search image feature vectors classified into a cluster selected for the one of the plurality of query image feature vectors.

3. The image search device according to claim 2 , wherein:

in the selection of the cluster, clusters corresponding to the query image feature vectors are selected based on distances between a plurality of representative feature vectors that respectively represent the plurality of clusters and the query image feature vectors.

4. The image search device according to claim 2 , wherein in the selection of the search image feature vector, for each of the plurality of query image feature vectors, all the search image feature vectors that satisfy conditions are selected from the plurality of search image feature vectors belonging to the cluster selected for the one of the plurality of query image feature vectors, the conditions are that a number of selected search image feature vectors is not more than one for each of the search images and that the selected search image feature vector is not selected for other query image feature vectors.

5. The image search device according to claim 2 , wherein the plurality of instructions further causes the processor to:

extract a search image feature vector from each of the search images; and

generate a plurality of clusters into which at least a part of the extracted search image feature vector is classified,

wherein in the generation of the cluster, the plurality of clusters are generated so that a number of search image feature vectors corresponding to any one of the plurality of search images among the search image feature vectors belonging to a given cluster does not exceed a predetermined value.

6. An image search method, comprising the steps of:

obtaining a plurality of query image feature vectors, each of said plurality of query image feature vectors indicating a local feature of a query image;

selecting, for each of the plurality of query image feature vectors, search image feature vectors from a plurality of search image feature vectors respectively indicating local features of each search image, which are stored in a storage unit in advance for each of the search images;

generating a score indicating a degree of similarity between each of the plurality of search images and the query image based on the search image feature vectors selected relative to the plurality of query image feature vectors; and

selecting an image from the plurality of search images based on the score generated for the search image,

wherein in the step of the selecting the search image feature vectors, an already-selected image list is initialized for each of the query image feature vectors, one or more search image feature vectors are selected for the query image feature vectors, not more than one search image feature vector is selected from the one or more selected search image feature vectors, the not more than one selected search image feature vector has not been extracted from an image included in the already-selected image list, and the image from which the not more than one selected search image feature vector has been extracted is added to the already-selected image list.

7. A non-transitory computer-readable information storage medium having stored thereon a program for causing a computer to:

obtain a plurality of query image feature vectors, each of said plurality of query image feature vectors indicating a local feature of a query image;

select, for each of the plurality of query image feature vectors, search image feature vectors which indicate local features of each search image, which are stored in storage means in advance for each of the search images;

generate a score indicating a degree of similarity between each of the plurality of search images and the query image based on the search image feature vectors selected relative to the plurality of query image feature vectors; and

select at least one search image from the plurality of search images based on the score generated for the search image,

wherein in the processing of selecting the search image feature vectors, an already-selected image list is initialized for each of the query image feature vectors, one or more search image feature vectors are selected for the query image feature vectors, not more than one search image feature vector is selected from the one or more selected search image feature vectors, the not more than one selected search image feature vector has not been extracted from an image included in the already-selected image list, and the image from which the not more than one selected search image feature vector has been extracted is added to the already-selected image list.

8. The image search device according to claim 1 , wherein in the selection of the search image feature vector, not more than one search image feature vector is arbitrarily selected, for each of the plurality of query image feature vectors, from a plurality of unselected search image feature vectors, the unselected search image feature vectors being the plurality of search image feature vectors and having not yet been selected for the query image feature vectors.

9. The image search device according to claim 8 , wherein the plurality of instructions further causes the processor to:

select a cluster corresponding to each of the plurality of query image feature vectors from a plurality of clusters into which a plurality of search image feature vectors indicating features of the plurality of search images are classified,

wherein in the selection of the search image feature vector, the search image feature vector is selected, for each of the plurality of query image feature vectors, from the plurality of search image feature vectors classified into a cluster selected for the corresponding one of the plurality of query image feature vectors.

10. The image search device according to claim 9 , wherein:

in the selection of the cluster, clusters corresponding to the query image feature vectors are selected based on distances between a plurality of representative feature vectors that respectively represent the plurality of clusters and the query image feature vectors.

11. The image search device according to claim 9 , wherein in the selection of the search image feature vector, for each of the plurality of query image feature vectors, all the search image feature vectors that satisfy conditions are selected from the plurality of search image feature vectors belonging to the cluster selected for the corresponding one of the plurality of query image feature vectors, the conditions are that a number of selected search image feature vectors is not more than one for each of the search images and that the selected search image feature vector is not selected for other query image feature vectors.

12. The image search device according to claim 3 , wherein in the selection of the search image feature vector, for each of the plurality of query image feature vectors, all the search image feature vectors that satisfy conditions are selected from the plurality of search image feature vectors belonging to the cluster selected for the corresponding one of the plurality of query image feature vectors, the conditions are that a number of selected search image feature vectors is not more than one for each of the search images and that the selected search image feature vector is not selected for other query image feature vectors.

13. The image search device according to claim 10 , wherein in the selection of the search image feature vector, for each of the plurality of query image feature vectors, all the search image feature vectors that satisfy conditions are selected from the plurality of search image feature vectors belonging to the cluster selected for the corresponding one of the plurality of query image feature vectors, the conditions are that a number of selected search image feature vectors is not more than one for each of the search images and that the selected search image feature vector is not selected for other query image feature vectors.

14. The image search device according to claim 3 , wherein the plurality of instructions further causes the processor to:

extract a search image feature vector from each of the search images; and

generate a plurality of clusters into which at least a part of the extracted search image feature vector is classified,

wherein in the generation of the cluster, the plurality of clusters are generated so that a number of search image feature vectors corresponding to any one of the plurality of search images among the search image feature vectors belonging to a given cluster does not exceed a predetermined value.

15. The image search device according to claim 4 , wherein the plurality of instructions further causes the processor to:

extract a search image feature vector from each of the search images; and

generate a plurality of clusters into which at least a part of the extracted search image feature vector is classified,

wherein in the generation of the cluster the plurality of clusters are generated so that a number of search image feature vectors corresponding to any one of the plurality of search images among the search image feature vectors belonging to a given cluster does not exceed a predetermined value.

16. The image search device according to claim 9 , wherein the plurality of instructions further causes the processor to:

extract a search image feature vector from each of the search images; and

generate a plurality of clusters into which at least a part of the extracted search image feature vector is classified,

wherein in the generation of the cluster the plurality of clusters are generated so that a number of search image feature vectors corresponding to any one of the plurality of search images among the search image feature vectors belonging to a given cluster does not exceed a predetermined value.

17. The image search device according to claim 10 , wherein the plurality of instructions further causes the processor to:

extract a search image feature vector from each of the search images; and

generate a plurality of clusters into which at least a part of the extracted search image feature vector is classified,

wherein in the generation of the cluster, the plurality of clusters are generated so that a number of search image feature vectors corresponding to any one of the plurality of search images among the search image feature vectors belonging to a given cluster does not exceed a predetermined value.

18. The image search device according to claim 11 , wherein the plurality of instructions further causes the processor to:

extract a search image feature vector from each of the search images; and

generate a plurality of clusters into which at least a part of the extracted search image feature vector is classified,

wherein in the generation of the cluster, the plurality of clusters are generated so that a number of search image feature vectors corresponding to any one of the plurality of search images among the search image feature vectors belonging to a given cluster does not exceed a predetermined value.

19. The image search device according to claim 12 , wherein the plurality of instructions further causes the processor to:

extract a search image feature vector from each of the search images; and

generate a plurality of clusters into which at least a part of the extracted search image feature vector is classified,

wherein in the generation of the cluster, the plurality of clusters are generated so that a number of search image feature vectors corresponding to any one of the plurality of search images among the search image feature vectors belonging to a given cluster does not exceed a predetermined value.

20. The image search device according to claim 13 , wherein the plurality of instructions further causes the processor to:

extract a search image feature vector from each of the search images; and

generate a plurality of clusters into which at least a part of the extracted search image feature vector is classified,

wherein in the generation of the cluster, the plurality of clusters are generated so that a number of search image feature vectors corresponding to any one of the plurality of search images among the search image feature vectors belonging to a given cluster does not exceed a predetermined value.

21. The image search device according to claim 1 , wherein in the selection of the search image feature vectors, not more than one search image feature vector is sequentially selected for each of the plurality of query feature vectors, wherein the selected search image feature vector has not yet been selected as matching the plurality of query image feature vectors and is extracted from a search image where any of search image feature vectors having not yet selected as matching the query feature vector.