Quantization method for feature vector, search method, apparatus and storage medium

A search method comprising:

• setting groups of quantization codewords between which a distance is different depending on a layer;
• selecting, from a group of quantization codewords between which a distance is shorter in a layer of layers of the set groups of quantization codewords, at least one quantization codeword of which distance from an original feature vector is smaller than first predetermined distance;
• determining quantization feature vectors corresponding to the original feature vector based on a projection distance of projecting the original feature vector on a line connecting a combination of at least one selected quantization codeword and any other quantization codeword belonging to a layer in which the distance is longer than that in a layer to which the selected quantization codeword belongs;
• storing the quantization feature vectors in a database;
• calculating distances of a feature vector to be looked up from the quantization feature vectors in the database;
• and
• determining, as a search result, at least one quantization feature vector for which distances satisfy a condition,
• wherein the quantization feature vectors are expressed using a ratio when the line connecting the two quantization codewords is internally divided or externally divided.

A non-transitory computer-readable storage medium storing instructions for causing a computer to perform a search method when executed by the computer, the search method comprising:

• setting groups of quantization codewords between which a distance is different depending on a layer;
• selecting, from a group of quantization codewords between which a distance is shorter in a layer of layers of the set groups of quantization codewords, at least one quantization codeword of which distance from an original feature vector is smaller than first predetermined distance;
• determining quantization feature vectors corresponding to the original feature vector based on a projection distance of projecting the original feature vector on a line connecting a combination of at least one selected quantization codeword and any other quantization codeword belonging to a layer in which the distance is longer than that in a layer to which the selected quantization codeword belongs;
• storing the quantization feature vectors in a database;
• calculating distances of a feature vector to be looked up from the quantization feature vectors in the database;
• and
• determining, as a search result, at least one quantization feature vector for which distances satisfy a condition,
• wherein the quantization feature vectors are expressed using a ratio when the line connecting the two quantization codewords is internally divided or externally divided.

A quantization apparatus comprising:

• one or more processors programmed to cause the quantization apparatus to function as:
• a setting unit configured to set groups of quantization codewords between which a distance is different depending on a layer;
• a selecting unit configured to select, from a group of quantization codewords between which a distance is shorter in a layer of layers of the set groups of quantization codewords, at least one quantization codeword of which distance from an original feature vector is smaller than first predetermined distance;
• and
• a quantization unit configured to determine quantization feature vectors corresponding to the original feature vector based on a projection distance of projecting the original feature vector on a line connecting a combination of at least one selected quantization codeword and any other quantization codeword belonging to a layer in which the distance is longer than that in a layer to which the selected quantization codeword belongs,
• wherein the quantization feature vectors are expressed using a ratio when the line connecting the two quantization codewords is internally divided or externally divided.

A search apparatus comprising:

• one or more processors programmed to cause the search apparatus to function as:
• a setting unit configured to set groups of quantization codewords between which a distance is different depending on a layer;
• a selecting unit configured to select, from a group of quantization codewords between which a distance is shorter in a layer of layers of the set groups of quantization codewords, at least one quantization codeword of which distance from an original feature vector is smaller than first predetermined distance;
• a quantization unit configured to determine quantization feature vectors corresponding to the original feature vector based on a projection distance of projecting the original feature vector on a line connecting a combination of at least one selected quantization codeword and any other quantization codeword belonging to a layer in which the distance is longer than that in a layer to which the selected quantization codeword belongs;
• a storing unit configured to store the quantization feature vectors in a database;
• a calculating unit configured to calculate distances of a feature vector to be looked up from the quantization feature vectors in the database;
• and
• a determining unit configured to determine, as a search result, at least one quantization feature vector for which distances satisfy a condition,
• wherein the quantization feature vectors are expressed using a ratio when the line connecting the two quantization codewords is internally divided or externally divided.

A non-transitory computer-readable storage medium storing instructions for causing a computer to perform a quantization method when executed by the computer, the quantization method comprising:

• setting groups of quantization codewords between which a distance is different depending on a layer;
• selecting, from a group of quantization codewords between which a distance is shorter in a layer of layers of the set groups of quantization codewords, at least one quantization codeword of which distance from an original feature vector is smaller than first predetermined distance;
• and
• determining quantization feature vectors corresponding to the original feature vector based on a projection distance of projecting the original feature vector on a line connecting a combination of at least one selected quantization codeword and any other quantization codeword belonging to a layer in which the distance is longer than that in a layer to which the selected quantization codeword belongs,
• wherein the quantization feature vectors are expressed using a ratio when the line connecting the two quantization codewords is internally divided or externally divided.