Vector quantization method and apparatus

• US 5,194,864 A
• Filed: 10/01/1991
• Issued: 03/16/1993
• Est. Priority Date: 10/03/1990
• Status: Expired due to Term

• Current Assignee: Olympus Optical Company Ltd. (Olympus Corporation)
• Original Assignee: Olympus Optical Company Ltd. (Olympus Corporation)
• Inventors: Nakano, Keiichi
• Primary Examiner(s): Pellinen, A. D.
• Assistant Examiner(s): Young, Brian K.
• Application Number:
  US07/770,987
• Time in Patent Office: 532 Days
• Field of Search: 341/106, 341/51, 341/65, 341/67, 341/155, 341/200, 358/133, 358/261.2, 358/136, 358/12, 381/41, 381/42
• US Class Current: 341/106
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

In a vector quantization method and apparatus of the invention, in the network learning step, learning is performed such that output units corresponding to the indexes of a plurality of code book vectors Yi are caused to ignite more as the output units are located nearer to an input vector. The search order is determined such that the code book vectors are searched in the order of the indexes corresponding to the decreasing magnitudes of ignition from the output units. In the strain calculation step, the strains between the code book vectors Yi selected in the determined order and the input vector X are calculated in units of dimensions. The current partial sum of strains is compared with the minimum stain. If the partial sum is larger than the minimum strain, the subsequent strain calculation is interrupted.

Claims

1. A vector quantization method comprising the steps of:

generating a network for performing a learning operation on the basis of a code book, in which specific representative vectors respectively having indexes assigned thereto are stored, such that output units for outputting in accordance with indexes of code book vectors Yi are caused to output larger outputs as said output units are located nearer to an input vector input to one of said output units;

causing said output units to output in accordance with an input vector X input to said network, and determining a search order to search the code book vectors Yi in the order of the indexes corresponding to decreasing change amounts in output;

performing strain calculation by sequentially calculating strains between the code book vectors Yi selected in the search order and the input vector X in units of dimensions;

comparing a partial sum of strains obtained by the strain calculation step with a minimum strain; and

interrupting the strain calculation when the partial sum becomes larger than the minimum strain.

2. A method according to claim 1, wherein:

the step of performing strain calculation comprises the steps of performing initialization by calculating a strain between a first code book vector Y1 and the input vector X and setting the calculated strain as a minimum strain, and calculating a partial sum of strains by calculating strains between the second and subsequent code book vectors Yi and the input vector X in units of dimensions, and

the comparing step comprises the steps of comparing the partial sum in each dimension with the minimum strain, and, when the partial sum through the dimensions becomes smaller than the minimum strain, setting the total sum as a new minimum strain.

3. A vector quantization method according to claim 1, comprising the steps of:

calculating absolute values of differences between the average values of code book vectors in the respective dimensions and the input vector in units of dimensions; and

setting a selection order in the steps of calculating the partial sum of strains such that calculation target components are selected in the order in which the absolute values of said differences are decreased.

4. A vector quantization apparatus comprising:

network generating means for generating a network for performing a learning operation such that output units corresponding to indexes of a plurality of code book vectors Yi have separation capabilities to output larger outputs as code book vectors corresponding to said output units are located nearer to an external input vector X;

search order determining means for causing said output units to output in accordance with the input vector X input to said network generating means, and determining a search order to search code book vectors in the order of the indexes corresponding to decreasing change amounts in output;

strain calculating means for sequentially calculating strains between the code book vectors Yi selected in the search order and the input vector X in units of dimensions;

comparing means for comparing a partial sum of strains obtained by said strain calculating means with a minimum strain; and

strain calculation interrupting means for interrupting the strain calculation when the partial sum becomes larger than the minimum strain.

5. An apparatus according to claim 4, wherein said strain calculating means comprises means for performing initialization by calculating a strain between a first code book vector Y1 and the input vector X and setting the calculated strain as a minimum strain, and means for calculating a partial sum of strains by calculating strains between a second and subsequent code book vectors Yi and the input vector X in units of dimensions, and

said comparing means comprises means for comparing the partial sum in each dimension with the minimum strain, and when the partial sum through the dimensions becomes smaller than the minimum strain, setting the total sum as a new minimum strain.

6. A vector quantization apparatus according to claim 4, comprising:

average value calculating means for calculating average values of vectors constituting a code book in units of dimensions;

difference calculating means for obtaining absolute values of differences between the average values obtained by said average value calculating means and the input vector in units of dimensions; and

calculation order determining means for determining a calculation order to calculate strains in the order in which the absolute values of the differences obtained by said difference calculating means are decreased.

7. A vector quantization method comprising the steps of:

generating a network for performing a learning operation on the basis of a code book, in which specific representative vectors respectively having indexes assigned thereto are stored, such that output units for outputting in accordance with indexes of code book vectors Yi are caused to output larger outputs as said output units are located nearer to an input vector input to one of said output units;

causing said output units to output in accordance with an input vector X input to said network, and determining a search order to search the code book vectors Yi in the order of the indexes corresponding to decreasing change amounts in output;

performing strain calculation by sequentially calculating strains between the code book vectors Yi selected in the search order and the input vector X in units of dimensions designated in advance;

comparing a partial sum of strains obtained by the strain calculation step with a minimum strain; and

interrupting the strain calculation when the partial sum becomes larger than the minimum strain.

8. A vector quantization method according to claim 7, comprising the steps of:

calculating absolute values of differences between the average values of code book vectors in the respective dimensions and the input vector in units of dimensions; and

setting a selection order in the steps of calculating the partial sum of strains such that calculation target components are selected in the order in which the absolute values of said differences are decreased.

9. A vector quantization apparatus comprising:

network generating means for generating a network for performing a learning operation such that output units corresponding to indexes of a plurality of code book vectors Yi have separation capabilities to output larger outputs as code book vectors corresponding to said output units are located nearer to an external input vector X;

search order determining means for causing said output units to output in accordance with the input vector X input to said network generating means, and determining a search order to search code book vectors in the order of the indexes corresponding to decreasing change amounts in output;

an index increment table for indicating a present number of dimensions, and storing an index with which strain calculation interruption is to be executed;

strain calculating means for sequentially calculating strains between the code book vectors Yi selected in the search order and the input vector X in units of dimensions preset by said index increment table;

comparing means for comparing a partial sum of strains obtained by said strain calculating means with a minimum strain; and

strain calculation interrupting means for interrupting the strain calculation when the partial sum becomes larger than the minimum strain.

10. A vector quantization apparatus according to claim 9, comprising:

average value calculating means for calculating average values of vectors constituting a code book in units of dimensions;

difference calculating means for obtaining absolute values of differences between the average values obtained by said average value calculating means and the input vector in units of dimensions; and

calculation order determining means for determining a calculation order to calculate strains in the order in which the absolute values of the differences obtained by said difference calculating means are decreased.

11. A vector quantization method comprising the steps of:

setting a minimum strain as an upper limit value, the minimum strain being obtained within a completed search operation by comparison between an input vector and code book vectors;

setting a sum of minimum strains as a lower limit value, the minimum strains being calculated between base values belonging to at least one of a code book vector providing a minimum strain and code book vectors which are not searched yet, and base values belonging to the input vector, in units of dimensions;

performing a storing/comparing operation by storing and comparing the lower and upper limit values;

performing a search terminating operation by terminating a search operation when the upper and lower limit values are compared and coincide with each other in the storing/comparing operation;

calculating a partial sum of strains between code book vectors up to a predetermined dimensional component and the input vector in units of dimensions when the search operation is not terminated in the search terminating operation;

comparing the partial sum with the upper limit, and interrupting the strain calculation when the partial sum is not less than the upper limit value; and

performing an upper limit value updating operation, when the partial sum through the dimensions is smaller than the upper limit, by setting the total sum as a new upper limit value.

12. A method according to claim 11, further comprising the step of calculating absolute values of differences between average values of code book vectors in the respective dimensions and the input vector in units of dimensions, and setting a selection order in the step of calculating the partial sum of strains such that calculation target components are selected in the order in which the absolute values of the differences are decreased.

13. A vector quantization apparatus comprising:

upper limit value setting means for setting a minimum strain as an upper limit value, the minimum strain being obtained within a completed search operation by comparison between an input vector and code book vectors;

sort means for sorting vectors, which constitute a code book and comprise components in a plurality of dimensions, into individual component values as base values in units of dimensions;

lower limit value setting means for calculating a sum of strains through the dimensions between base values belonging to at least one of a code book vector providing a minimum strain and code book vectors which are not searched yet, and base values belonging to the input vector in units of dimensions;

storing/comparing means for storing and comparing the lower and upper limit values;

search terminating means for terminating a search operation when the upper and lower limit values are compared by said storing/comparing means and coincide with each other;

a partial strain sum calculating means for calculating a partial sum of strains between code book vectors up to a predetermined dimensional component and the input vector in units of dimensions when the search operation is not terminated by said search terminating means;

strain calculating interrupting means for comparing the partial sum with the upper limit, and interrupting the strain calculation when the partial sum is not less than the upper limit value; and

upper limit value updating means for performing an upper limit value updating operation, when the partial sum through the dimensions is smaller than the upper limit, by setting the total sum as a new upper limit value.

14. A vector quantization apparatus according to claim 13, comprising:

average value calculating means for calculating average values of vectors constituting a code book in units of dimensions;

difference calculating means for obtaining absolute values of differences between the average values obtained by said average value calculating means and the input vector in units of dimensions; and

calculating order determining means for determining a calculation order to calculate strains in the order in which the absolute values of the differences obtained by said difference calculating means are decreased.