# US 2019/0377751 A1 · Quantization method for feature vector, search method, apparatus and storage medium > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0377751 A1 - Document ID: US20190377751A1 - Status: Published application - Kind: A1 - Application number: 16/431,520 - Filed: 2019-06-04 - Published: 2019-12-12 - Earliest claimed: 2018-06-07 - Assignees: Canon Kabushiki Kaisha - Applicants: Canon Kabushiki Kaisha - Inventors: Yaohai Huang; Cheng Tan; Yuanda Deng - Web page: https://patentgrep.com/patent/US20190377751A1 ## CPC - G06F 16/56: having vectorial format - G06F 16/53: Querying - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Embodiments of the present disclosure provide a quantization method of feature vector, search method, apparatus and storage medium, wherein the quantization method comprises: setting quantization codewords; selecting, from the set quantization codewords, at least one quantization codeword of which distance from an original feature vector is smaller than first predetermined distance as a quantization codeword subset; determining quantization feature vectors corresponding to the original feature vector by using at least two quantization codewords, wherein at least one quantization codeword from the at least two quantization codewords are in the quantization codeword subset. The search method is a method of performing a search among quantization feature vectors after a quantization using the quantization method. ## Claims ### Claim 1 A quantization method comprising: setting quantization codewords; selecting, from the set quantization codewords, at least one quantization codeword of which distance from an original feature vector is smaller than first predetermined distance as a quantization codeword subset; and determining quantization feature vectors corresponding to the original feature vector by using at least two quantization codewords, wherein at least one quantization codeword from the at least two quantization codewords are in the quantization codeword subset. ### Claim 2 (depends on 1) The quantization method according to claim 1, wherein the selecting the quantization codeword subset from the set quantization codewords comprises: selecting the quantization codeword subset from quantization codewords set in a hierarchy structure. ### Claim 3 (depends on 2) The quantization method according to claim 2, wherein the quantization codewords set in the hierarchy structure include top layer quantization codewords and sub layer quantization codewords corresponding to the top layer quantization codewords; the selecting the quantization codeword subset from the set quantization codewords comprising: calculating distance of the original feature vector from each of top layer quantization codewords; and selecting, as the quantization codeword subset, at least one top layer quantization codeword of which distance from the original feature vector satisfies a setting distance requirement and sub layer quantization codewords corresponding to the top layer quantization codeword. ### Claim 4 (depends on 3) The quantization method according to claim 3, wherein at least one top layer quantization codeword of which distance from the original feature vector satisfies the setting distance requirement and the sub layer quantization codewords corresponding to the top layer quantization codeword are divided into sets, and at least one divided set is selected as the quantization codeword subset. ### Claim 5 (depends on 3) The quantization method according to claim 3, wherein the determining quantization feature vectors corresponding to the original feature vector by using at least two quantization codewords comprises: performing, when a top layer quantization codeword from the quantization codeword subset is present in the quantization codewords for determining the quantization feature vectors corresponding to the original feature vector and when the original feature vector is divided into a plurality of sub feature vectors, a quantization processing on each of the sub feature vectors divided from the original feature vector by using the top layer quantization codeword and the sub layer quantization codewords corresponding thereto. ### Claim 6 (depends on 5) The quantization method according to claim 5, further comprising: storing the determined quantization feature vectors by the following information: information of two quantization codewords for determining a quantization feature vector corresponding to the original feature vector, information of two quantization codewords used in performing the quantization processing on each of the sub feature vectors and parameters. ### Claim 7 (depends on 6) The quantization method according to claim 6, wherein the parameter is, in considering of directionality, a ratio of a distance of the sub feature vector to a nearer quantization codeword of the two quantization codewords used in performing the quantization processing, to a distance between the two quantization codewords. ### Claim 8 (depends on 1) The quantization method according to claim 1, wherein when the number of quantization codewords for determining quantization feature vectors corresponding to the original feature vector is more than two, quantization feature vectors obtained based on any two quantization codewords are determined and one quantization feature vector is selected from the determined quantization feature vectors as a quantization feature vector corresponding to the original feature vector. ### Claim 9 (depends on 1) The quantization method according to claim 1, wherein the determining quantization feature vectors corresponding to the original feature vector by using at least two quantization codewords comprises: connecting any two quantization codewords in the at least two quantization codewords with one another, and calculating vertical projections of the original feature vector on each of connection lines respectively; and determining a connection line on which projection distance satisfies a requirement, and determining, as a quantization feature vector corresponding to the original feature vector, a projection of the original feature vector on the connection line on which the projection distance satisfies the requirement. ### Claim 10 (depends on 9) The quantization method according to claim 9, wherein the determined quantization feature vector is represented by information of at least two quantization codewords for determining quantization feature vectors corresponding to the original feature vector and at least one parameter. ### Claim 11 (depends on 10) The quantization method according to claim 10, wherein the parameter is, in considering of directionality, a ratio of a distance of a quantization feature vector obtained by projecting the original feature vector on a connection line constituted by two quantization codewords to a nearer quantization codeword of the two quantization codewords, to a distance between the two quantization codewords, and the number of parameters is equal to the number of connection lines constituted by the at least two quantization codewords. ### Claim 12 (depends on 11) The quantization method according to claim 11, wherein preset values of parameter are distributed in a specific area of a feature space, and if a calculation value of parameter determined in performing the calculation of vertical projections is within the specific area, a preset value of parameter closest to the calculation value of parameter is taken as the parameter for presenting quantization feature vectors; and if the calculation value of parameter determined in performing the calculation of vertical projections is not within the specific area, a value of an upper limit value and a lower limit value which is closer to the calculation value of parameter is taken as the parameter for presenting quantization feature vectors. ### Claim 13 (depends on 1) The quantization method according to claim 1, the determining quantization feature vectors corresponding to the original feature vector when at least two quantization codewords for determining quantization feature vectors corresponding to the original feature vector are all from the quantization codeword subset comprising: selecting, from the quantization codeword subset, at least one quantization codeword of which distance from the original feature vector satisfies a condition; calculating, by connecting each of quantization codewords selected from the quantization codeword subset with other quantization codewords in the quantization codeword subset respectively, vertical projections of the original feature vector on each of connection lines; and determining a connection line on which projection distance satisfies a requirement, and determining, as a quantization feature vector corresponding to the original feature vector, a projection of the original feature vector on the connection line on which the projection distance satisfies the requirement. ### Claim 14 (depends on 13) The quantization method according to claim 13, the calculating, by connecting each of quantization codewords selected from the quantization codeword subset with other quantization codewords in the quantization codeword subset respectively, vertical projections of the original feature vector on each of connection lines comprising: sequentially connecting, in order of distances of quantization codewords selected from the quantization codeword subset from the original feature vector from near to far, each of quantization codewords with other quantization codewords in the quantization codeword subset respectively; and finishing, when calculation number of vertical projections of the original feature vector on connection lines exceeds a set maximum value, calculation of vertical projections of the original feature vector. ### Claim 15 (depends on 1) A search method comprising: calculating distances of a feature vector to be looked up from quantization feature vectors after a quantization using the quantization method according to claim 1 in a database; and determining, as a search result, at least one quantization feature vector for which distances satisfy a condition. ### Claim 16 (depends on 15) The search method according to claim 15, wherein the calculating distances of the feature vector to be looked up from quantization feature vectors comprises: determining, among quantization codewords set in a feature space, a top layer quantization codeword of which distance from the feature vector to be looked up is smaller than second predetermined distance, and determining, among sub layer quantization codewords corresponding to the top layer quantization codeword, sub layer quantization codewords of which distances from the feature vector to be looked up are smaller than third predetermined distance; determining quantization feature vectors obtained by using the determined top layer quantization codeword and/or the determined sub layer quantization codewords; and calculating distances between the feature vector to be looked up and the determined quantization feature vectors. ### Claim 17 (depends on 1) 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: calculating distances of a feature vector to be looked up from quantization feature vectors after a quantization using the quantization method according to claim 1 in a database; and determining, as a search result, at least one quantization feature vector for which distances satisfy a condition. ### Claim 18 A quantization apparatus comprising: a setting unit, configured to set quantization codewords; a selecting unit, configured to select, from the set quantization codewords, at least one quantization codeword of which distance from an original feature vector is smaller than first predetermined distance as a quantization codeword subset; and a quantization unit, configured to determine quantization feature vectors corresponding to the original feature vector by using at least two quantization codewords, wherein at least one quantization codeword from the at least two quantization codewords are in the quantization codeword subset. ### Claim 19 (depends on 18) A search apparatus comprising: a calculating unit, configured to calculate distances of a feature vector to be looked up from quantization feature vectors after a quantization using the quantization apparatus according to claim 18, which are stored in a database; and a determining unit, configured to determine, as a search result, at least one quantization feature vector for which distances satisfy a condition. ### Claim 20 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 quantization codewords; selecting, from the set quantization codewords, at least one quantization codeword of which distance from an original feature vector is smaller than first predetermined distance as a quantization codeword subset; and determining quantization feature vectors corresponding to the original feature vector by using at least two quantization codewords, wherein at least one quantization codeword from the at least two quantization codewords are in the quantization codeword subset.