Image search apparatus and image search method

An image search method comprising:

• approximate-space searching step of using approximate data produced by reducing dimensions of multidimensional feature data extracted from an image, comparing the approximate data produced by reducing dimensions of the multidimensional feature data to approximate data corresponding to a search key, and, based on a result of said comparing, arranging image groups stored in an image storing unit in order of similarity with an image to be searched;
• and
• real-space final ranking step of performing a distance re-calculation using the multidimensional feature data used to produce the approximate data produced by said reducing dimensions, on a group of results in which the similarity obtained in the approximate-space searching step is high, and determining final rankings,
• wherein the distance recalculation is performed using the multidimensional feature data used to produce the approximate data produced by said reducing dimensions, in descending order of elements in which the similarity obtained by the approximate-space searching step is high (i.e., in ascending order of the approximate distance), the process is completed at a timing when top K pieces of actual distances which are obtained by the recalculation and in which the similarity is high are smaller than an approximate distance of all data that are not subjected to the distance recalculation, and the top K pieces of distances are output as the search result.

An image search apparatus comprising:

• a processor, comprising:
• an image storing unit configured to store an image;
• an approximate-data storing unit including a memory and configured to store approximate data of the image in association with the image, the approximate data produced from the image so as to reflect similarity to a search key;
• an approximate-space searching unit configured to search approximate data of the search key from the approximate data stored in the approximate-data storing unit;
• and
• a calculating unit configured to calculate similarity between the search key and the image which is stored in the image storing unit and corresponds to a search result output from the approximate-space searching unit, the calculating unit including a real-space final ranking unit that performs a distance calculation of distances from multidimensional feature data used to produce the approximate data, to corresponding data of the search key, on a group of results in which a similarity obtained by the approximate-space searching unit is high, determines final rankings, and outputs the final rankings as a search result,
• wherein the real-space final ranking unit performs a distance recalculation using the multidimensional feature data used to produce the approximate data, in descending order of elements in which the similarity obtained by the approximate-space searching unit is high (i.e., in ascending order of the approximate distance), completes the process at a timing when top K pieces of actual distances which are obtained by the recalculation and in which the similarity is high are smaller than an approximate distance of all data that are not subjected to the distance recalculation, and outputs the top K pieces of distances as the search result.

A data storage device in an image search apparatus, said device comprising:

• an image storing unit configured to store an image;
• and
• an approximate-data storing unit configured to store approximate data obtained by approximating the image in association with the image stored in the image storing unit, the approximate data produced from the image so as to reflect similarity to a search key;
• an approximate-space searching unit configured to search approximate data of the search key from the approximate data stored in the approximate-data storing unit;
• a real-space final ranking unit that performs a distance calculation of distances from multidimensional feature data used to produce the approximate data, to corresponding data of the search key, on a group of results in which a similarity obtained by the approximate-space searching unit is high, determines final rankings, and outputs the final rankings as a search result;
• wherein the real-space final ranking unit performs a distance recalculation using the multidimensional feature data used to produce the approximate data, in descending order of elements in which the similarity obtained by the approximate-space searching unit is high (i.e., in ascending order of the approximate distance), completes the process at a timing when top K pieces of actual distances which are obtained by the recalculation and in which the similarity is high are smaller than an approximate distance of all data that are not subjected to the distance recalculation, and outputs the top K pieces of distances as the search result;
• wherein an amount of data stored in the approximate-data storing unit is smaller than an amount of data in the image storing unit which stores the image corresponding to the approximate data, and
• wherein the approximate-data storing unit comprises a memory accessible at a speed higher than that of the image storing unit.