Full-search-equivalent method for matching data and a vector quantizer utilizing such method
First Claim
1. A method for searching a set of representative elements to locate one element which closely matches an input element, the method comprising:
- (a) calculating the value of a characteristic measure for the input element,(b) identifying a reference element, Aj, having a value of the characteristic measure which satisfies a first criterion,(c) computing a distance, hI,j, between the input element and the reference element Aj,(d) identifying a subject, S, of representative elements for which a measure of the representative elements in the subset S satisfies a second criterion with respect to the reference element,(e) selecting a representative element from the subset S which closely matches the input element.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for compressing data employing vector quantization is achieved by calculating the norm of an input vector and identifying a reference codebook vector which has a norm which is closest to the norm of the input vector. The distance between the input vector and the reference codebook vector selected is computed and employed to identify a vector space about the reference vector containing a subset of codebook vectors one or more of which may be closer to the input vector than the initially selected reference vector. The closest codebook vector is selected iteratively without the necessity of searching every vector in the codebook.
-
Citations
23 Claims
-
1. A method for searching a set of representative elements to locate one element which closely matches an input element, the method comprising:
-
(a) calculating the value of a characteristic measure for the input element, (b) identifying a reference element, Aj, having a value of the characteristic measure which satisfies a first criterion, (c) computing a distance, hI,j, between the input element and the reference element Aj, (d) identifying a subject, S, of representative elements for which a measure of the representative elements in the subset S satisfies a second criterion with respect to the reference element, (e) selecting a representative element from the subset S which closely matches the input element.
-
-
2. A method for compressing data comprising the steps of:
-
(a) generating a set of codebook vectors, each codebook vector identified by a unique identification code, (b) organizing the data as a set of input vectors, (c) for each input vector; (i) calculating the value of a characteristic measure for the input vector, (ii) identifying a reference codebook vector, Aj, having a value of a measure which satisfies a first criterion, (iii) computing a distance, hI,j , between the input vector. and the reference codebook vector Aj, (iv) identifying a subset, S, of codebook vectors for which a measure of codebook vectors of the subset S satisfies a second criterion with respect to the reference vector, (v) selecting a codebook vector from the subset S which closely matches the input vector, (d) expressing each input vector as the identification code of the selected, closely matching codebook vector. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. An apparatus for compressing data in the form of an input vector into an identification code of one of a set of codebook vectors, said apparatus comprising:
-
(a) input means for receiving the input vector and codebook vectors, (b) memory means connected to the input means for storing the input vector and codebook vectors, (d) vector processor means connected to the memory means, said processor means comprising; (i) measuring means responsive to the input vector for calculating the value of a characteristic measure for the input vector; (ii) identification means responsive to the calculated characteristic measure for the input vector and to codebook vectors for identifying a reference codebook vector, Aj, having a value of the characteristic measure which satisfies a first criterion; (iii) computing means responsive to the identified reference codebook vector, Aj, and to the input vector for computing a distance, hI,j, between the input vector and the reference codebook vector Aj ; (iv) partitioning means responsive to the computed distance hI,j and to codebook vectors having identifying a subset, S, of codebook vectors having measures which satisfy a second criterion with repsect to the input vector, (v) comparing means responsive to the subset S of codebook vectors and to the input vector for selecting a codebook vector from the subset S, which closely matches the input vector, (e) output means connected to the processor means for generating an output signal, said signal output representative of the identification code of the closely matching codebook vector. - View Dependent Claims (18, 19)
-
-
20. A system for compressing and regenerating input vector data using codebook vectors, said system comprising:
-
(a) a source of input vector data; (c) a vector quantizer connected to said source for quantizing said data, said vector quantizer comprising; (i) input means for receiving an input vector, (11) memory means connected to the input means for storing said input vector and codebook vectors, (iii) vector processor means connected to the memory means, said processor means comprising; (A) measuring means responsive to the input vector for calculating the value of a characteristic measure for the input vector; (B) identification means responsive to the calculated characteristic measure for the input vector and to codebook vectors for identifying a reference codebook vector, Aj, having a value of the characteristic measure which satisfies a first criterion; (C) computing means responsive to the identified reference codebook vector, Aj, and to the input vector for computing a distance, hI,j, between the input vector and the reference codebook vector Aj ; (D) partitioning means responsive to the computed distance hi,j and to codebook vectors for identifying a subset, S, of codebook vectors having measures which satisfy a second criterion with respect to the reference vector, (E) comparing means responsive to the subset S of codebook vectors and to the input vector for selecting a codebook vector from the subset S, which closely matches the input vector; (iv) output means connected to the processor means for generating a compressed signal, said compressed signal representative of the identification code of the closely matching codebook vector; (e) regeneration means for approximately regenerating said data from said compressed signal. - View Dependent Claims (21, 22)
-
-
23. An apparatus for compressing data in the form of an input vector into an identification code of one of a set of codebook vectors, said apparatus comprising:
-
(a) input means for receiving the input means for storing the input data vector and for storing codebook vectors, (b) memory means connected to the input means for storing the input data vector and for storing codebook vectors, (d) vector processor means connected to the memory means for calculating the value of a characteristic measure for an input vector;
identifying a reference codebook vector, Aj, having a value of the characteristic measure which satisfies a first criterion;
computing a distance, hI,j, between the input vector and the reference codebook vector Aj ;
identifying a subset, S, of codebook vectors for which a measure of the codebook vectors satisfies a second criterion with respect to the reference vector; and
selecting a codebook vector from the subset S which closely matches the input vector,(e) output means connected to the vector processor means for generating an output signal representative of the identification code of the closely matching codebook vector.
-
Specification