US5255346A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for design of a vector quantizer
Assignee: Qwest Communications International Inc
•
Filing: 1989-12-28
•
Granted: 1993-10-19
•
Expires: 2009-12-28
Abstract
Abstract A method and apparatus for the design of a robust vector quantizer is disclosed. The initial output vector set is equal to the centroid of a training sequence of input vectors. A neural-network simulation and neighborhood functions are utilized for splitting and optimizing the output vectors. In this manner, the entire output vector set is sensitive to each input vector and therefore optimal output vector locations with respect to specified distortion criteria are obtained. The resulting vector quantizer is robust for the class of signals represented by the training sequence.
Inventors
- 👤 Frank H. Wu
- 👤 Kalyan Ganesan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 08:31
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/002; G06F; G06F18/00; G06F18/20; G06F18/24; G06F18/241; G06F18/2413; G06F18/24133; G06F18/24137; G06N; G06N3/00; G06N3/02; G06N3/04; G06N3/0499; G06N3/08; G06N3/082; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3082; H04; H04N; H04N19/00; H04N19/90; H04N19/94
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
304 words
A method for designing vector quantizers performed by a computer system including a processor, an input/output component and memory, wherein said method is controlled by said processor, the method comprising the steps of: (a) acquiring via said input/output component training sequence of input vectors; (b) forming a set of output vectors comprised of an initial output vector representative of said training sequence; (c) splitting each of said output vectors in said set of output vectors into new output vectors, thereby forming a new set of output vectors; (d) initializing a neighborhood as a function of the number of output vectors said set of output vectors; (e) simulating a neural-network by arranging said set of output vectors as a single-layer perceptron model and storing said single-layer perceptron model in said memory; (f) for each of said input vectors, performing the substeps of: (i) associating an associated output vector to said input vector, termed associated input vector, wherein said associated output vector is an output vector that is closest to said associated input vector; and (ii) readjusting and storing in said memory said associated output vector and all output vectors within said neighborhood of said associated output vector as a function of said associated input vector; (g) calculating a relative distortion level for said output vectors and said input vectors; (h) repeating steps (f) and (g) until said relative distortion level is less than or equal to a preselected optimization threshold level; (i) reducing said neighborhood incrementally and repeating steps (f)-(h) until said neighborhood is zero; and (j) repeating steps (c) through (i) until the number of output vectors in said set of output vectors equals a predetermined maximum number of output vectors, wherein each of said steps and substeps are controlled by the processor, and whereby said set of output vectors represents said training sequence.
Claim 2
Independent Claim
304 words
A method for designing vector quantizers performed by a computer system including a processor, an input/output component and memory, wherein said method is controlled by said processor, the method comprising the steps of: (a) acquiring via said input/output component training sequence of input vectors; (b) forming a set of output vectors comprised of an initial output vector representative of said training sequence; (c) splitting each of said output vectors in said set of output vectors into new output vectors, thereby forming a new set of output vectors; (d) initializing a neighborhood as a function of the number of output vectors said set of output vectors; (e) simulating a neural-network by arranging said set of output vectors as a single-layer perceptron model and storing said single-layer perceptron model in said memory; (f) for each of said input vectors, performing the substeps of: (i) associating an associated output vector to said input vector, termed associated input vector, wherein said associated output vector is an output vector that is closest to said associated input vector; and (ii) readjusting and storing in said memory said associated output vector and all output vectors within said neighborhood of said associated output vector as a function of said associated input vector; (g) calculating a relative distortion level for said output vectors and said input vectors; (h) repeating steps (f) and (g) until said relative distortion level is less than or equal to a preselected optimization threshold level; (i) reducing said neighborhood incrementally and repeating steps (f)-(h) until said neighborhood is zero; and (j) repeating steps (c) through (i) until the number of output vectors in said set of output vectors equals a predetermined maximum number of output vectors, wherein each of said steps and substeps are controlled by the processor, and whereby said set of output vectors represents said training sequence.
Claim 3
Dependent Claim
101 words
The method as claimed in claim 1, wherein said method includes the step of storing in said memory a prior distortion level equal to infinity after step (b), and wherein said step of calculating a relative distortion level includes the steps of (i) determining a total distortion level between said output vectors and said input vectors, (ii) deriving a relative distortion level from said total distortion level and a prior distortion level, which is said relative distortion level calculated during a previous iteration of steps (f) and (g), and (iii) setting said prior distortion level equal to said total distortion level.
Claim 4
Dependent Claim
52 words
The method as claimed in claim 1, wherein, after step (j), the method further comprises the steps of determining a rearrangement distance for each pair of output vectors and of eliminating from said memory one of said pair of output vectors if said rearrangement distance is less than a predetermined rearrangement threshold.
Claim 5
Dependent Claim
27 words
The method as claimed in claim 3, wherein the method further comprises repeating step (f) after said rearrangement distance is determined and said output vectors are eliminated.
Claim 6
Dependent Claim
69 words
The method as claimed in claim 3, wherein said rearrangement distance d is determined as: ##EQU6## where N is the dimension of said output vectors, w no is the n th element of a o th output vector, w np is the n th element of a p th output vector, and d op is the distance from said o th output vector to said p th output vector.
Claim 7
Dependent Claim
38 words
The method as claimed in claim 1, wherein, after step (j), the method further comprises the step of eliminating any output vector from said memory which does not serve as said associated output vector to any input vector.
Claim 8
Dependent Claim
24 words
The method as claimed in claim 6, wherein the method further comprises repeating step (f) after said step of eliminating output vectors is performed.
Claim 9
Dependent Claim
69 words
The method as claimed in claim 1, wherein said step of forming said set of output vectors includes the steps of calculating the centroid W[c] of said training sequence by: ##EQU7## where Q is the number of input vectors, and X[q] is an input vector in said training sequence, and of setting an N-dimensional initial output vector equal to W[c], where N is the dimension of said input vectors.
Claim 10
Dependent Claim
42 words
The method as claimed in claim 1, wherein the step of splitting an output vector W[i] is done in accordance with: W[a]=W[i]+δ.sub.1 W[i], W[b]=W[i]-δ.sub.1 W[i] where W[a] and W[b] are said new output vectors, and δ 1 is a predetermined perturbation value.
Claim 11
Dependent Claim
22 words
The method as claimed in claim 1, wherein said single-layer perceptron is comprised of said output vectors arranged in a two-dimensional grid.
Claim 12
Dependent Claim
29 words
The method as claimed in claim 10, wherein said step of initializing said neighborhood is performqd by calculating the largest dimension of said two-dimensional, grid and subtracting one therefrom.
Claim 13
Dependent Claim
106 words
The method as claimed in claim 1, wherein the step of associating an output vector W[i] to an input vector X[q] includes the step of calculating a distance d iq from an i th output vector to q th input vector as given by: ##EQU8## where N is the dimension of said input vectors, w ni is the n th element of the i th output vector, x ng is the n th element of the q th input vector and of selecting W[A] as the associated vector wherein d Aq is the smallest d iq , for i=1 to the number of output vectors M.
Claim 14
Dependent Claim
43 words
The method as claimed in claim 1, wherein the step of readjusting an output vector W[A] includes the step of calculating a new output vector W[A]' by: W[A]'=W[A]+η (X[q]-W[A]) where X[q] specifies said associated input vector and η is a predetermined gain term.
Claim 15
Dependent Claim
76 words
The method as claimed in claim 13, wherein said method includes the step of setting an iteration index P to zero when said neighborhood is initialized and incrementing said iteration index P each instance step (f) is repeated, and wherein said gain term η is given by ##EQU9## where k is the distance between an output node of an output vector W[i] and an output node of an output vector closest to an input vector X[q].
Claim 16
Dependent Claim
87 words
The method as claimed in claim 2, wherein said method includes the step of setting an iteration index P to zero when said neighborhood is initialized and incrementing said iteration index P each instance step (f) is repeated, and wherein said step of determining a total distortion level D P includes the step of measuring the sum of each of the distances from associated input vector and output vector pairs and is given by: ##EQU10## where Q is the number of input vectors in said training sequence.
Claim 17
Dependent Claim
18 words
The method as claimed in claim 15, wherein said relative distortion level D T is derived by: ##EQU11##
Claim 18
Dependent Claim
107 words
The method as claimed in claim 1, wherein said associating step (f)(i) is performed for each input vector before said readjusting substep (f)(ii) is performed, such that at the completion of step (f)(i) each output vector is associated with a set of associated input vectors, and said readjusting step (f)(ii) is performed in parallel for a group of said output vectors, such that each associated output vector in said group and all output vectors within said neighborhood of said associated output vector are readjusted as a function of said associated input vectors at substantially the same time as all other output vectors in said group are readjusted.
Claim 19
Dependent Claim
20 words
The method as claimed in claim 1, wherein said steps (f)(i) and (ii) are performed sequentially for each input vector.
Claim 20
Dependent Claim
269 words
A vector quantizer design system comprising: (a) an input/output component for receiving a training sequence of input vectors; (b) a memory; (c) processor control means for: (i) forming a set of output vectors comprised of an initial output vector representative of training sequence; and (ii) determining a set of output vectors by repeating, until the number of output vectors equals a predetermined maximum number of output vectors, the steps of: (1) splitting each of the output vectors in said set of output vectors into two new output vectors and thereby forming a new set of output vectors, (2) initializing a neighborhood as a function of the number of output vectors in said set of output vectors, (3) simulating a neural-network by arranging said set of output vectors as a single-layer perceptron model and storing said single-layer perceptron model in said memory, (4) performing, for each of said input vectors, the substeps of: (A) associating an output vector to said input vector wherein said associated output vector is the output vector closest to said input vector; and (B) readjusting and storing within said memory said associated output vector and all output vectors within said neighborhood of said associated output vector as a function of said input vector; (5) calculating a relative distortion level for said output vectors and said input vectors; (6) repeating steps (4) and (5) until said relative distortion level is less than or equal to a preselected optimization threshold level; and (7) reducing the neighborhood incrementally and repeating steps (1) through (6) until said neighborhood is zero, whereby said set of output vectors represents the training sequence.
Claim 21
Dependent Claim
269 words
A vector quantizer design system comprising: (a) an input/output component for receiving a training sequence of input vectors; (b) a memory; (c) processor control means for: (i) forming a set of output vectors comprised of an initial output vector representative of training sequence; and (ii) determining a set of output vectors by repeating, until the number of output vectors equals a predetermined maximum number of output vectors, the steps of: (1) splitting each of the output vectors in said set of output vectors into two new output vectors and thereby forming a new set of output vectors, (2) initializing a neighborhood as a function of the number of output vectors in said set of output vectors, (3) simulating a neural-network by arranging said set of output vectors as a single-layer perceptron model and storing said single-layer perceptron model in said memory, (4) performing, for each of said input vectors, the substeps of: (A) associating an output vector to said input vector wherein said associated output vector is the output vector closest to said input vector; and (B) readjusting and storing within said memory said associated output vector and all output vectors within said neighborhood of said associated output vector as a function of said input vector; (5) calculating a relative distortion level for said output vectors and said input vectors; (6) repeating steps (4) and (5) until said relative distortion level is less than or equal to a preselected optimization threshold level; and (7) reducing the neighborhood incrementally and repeating steps (1) through (6) until said neighborhood is zero, whereby said set of output vectors represents the training sequence.
References Cited (Backward Citations)
US3436752A
Cited
US4558350A
Cited
US4560977A
Cited
US4670851A
Cited
US4754258A
Cited
US4809067A
Cited
US4922508A
Cited
US4866645A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-10-18 | 1997-04-19 | 1997-10-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-10-18 | 2001-04-19 | 2001-10-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-10-18 | 2005-04-19 | 2005-10-19 | $7700.00 | Window Closed / Lapsed |