Method for generating a vector codebook, method and device for compressing data, and distributed speech recognition system

• US 8,214,204 B2
• Filed: 07/23/2004
• Issued: 07/03/2012
• Est. Priority Date: 07/23/2004
• Status: Active Grant

• Current Assignee: Telecom Italia S.p.A.
• Original Assignee: Telecom Italia S.p.A.
• Inventors: Ettorre, Donato, Bollano, Gianmario, Fodrini, Maurizio
• Primary Examiner(s): He, Jialong
• Application Number:
  US11/658,090
• Publication Number:
  US 20090037172A1
• Time in Patent Office: 2,902 Days
• Field of Search: 704/222, 704/201, 704/230, 704/270
• US Class Current: 704/222
• CPC Class Codes: G10L 15/30 Distributed recognition, e.g. in client-server systems, for mobile phones or network applications

Abstract

A method for compressing data, the data being represented by an input vector having Q features, wherein Q is an integer higher than 1, including the steps of 1) providing a vector codebook of sub-sets of indexed Q-feature reference vectors and threshold values associated with the sub-sets for a prefixed feature; 2) identifying a sub-set of reference vectors among the sub-sets by progressively comparing the value of a feature of the input vector which corresponds to the prefixed feature, with the threshold values associated with the sub-sets; and 3) identifying the reference vector which, within the sub-set identified in step 2), provides the lowest distortion with respect to the input vector.

Claims

1. A method, implemented by a computer, for generating a vector codebook providing low data compression computational effort starting from a vector codebook comprising a set of N reference vectors each comprising Q features, wherein N and Q are positive integers higher than 1, comprising the steps of:

a) sorting, by the computer, the set of N reference vectors in ascending or descending order with respect to values associated with a predetermined feature of the set of N reference vectors;

b) subdividing, by the computer, the set of sorted reference vectors in sub-sets;

c) associating, by the computer, with each of said sub-sets a respective threshold value for the predetermined feature;

d) sorting, by the computer, the reference vectors of each of said sub-sets in ascending or descending order with respect to values associated with a further predetermined feature of the set of N reference vectors;

e) subdividing, by the computer, each of said sub-sets of sorted reference vectors in further sub-sets;

f) associating, by the computer, with each of said further sub-sets a respective further threshold value for the further predetermined feature; and

g) extending at least one of the sub-sets obtained in step b) with at least one reference vector of an adjacent sub-set,

wherein steps d) and e) being carried out on the sub-sets extended according to step g),

wherein the set of N reference vectors sorted in step a) are arranged in a table form including N rows and Q columns, each row representing a reference vector having Q features.

2. The method according to claim 1, wherein the steps d), e), and f) are repeated for a predetermined number of times, considering each time as sub-sets the further sub-sets obtained in the previous execution of the further splitting and, for performing steps d) and f), another further predetermined feature of the set of N reference vectors.

3. The method according to claim 2, further comprising:

h) extending at least one of the further sub-sets obtained in step e) with at least one reference vector of an adjacent further sub-set, the steps d), e), and f) being repeated considering each time as sub-sets the further sub-sets extended according to the previous execution of step h).

4. The method according to claim 1, wherein step g) is carried out by extending the sub-set obtained in step b) which is at the top of the set sorted in step a) by adding at the bottom thereof at least one reference vector corresponding to the reference vector that, in the set sorted in step a), is immediately below such top sub-set.

5. The method according to claim 1, wherein step g) is carried out by extending the sub-set obtained in step b) which is at the bottom of the set sorted in step a) by adding at the top thereof at least one reference vector corresponding to the reference vector that, in the set sorted in step a), is immediately above such bottom sub-set.

6. The method according to claim 1, wherein step g) is carried out by extending any other central sub-set obtained in step b) by adding at the top and at the bottom thereof at least one reference vector corresponding to the reference vector that, in the set sorted in step b), is immediately above and below such central sub-set.

7. The method according to claim 1, further comprising:

h) extending at least one of the further sub-sets obtained in step e) with at least one reference vector of an adjacent further sub-set.

8. The method according to claim 7, wherein step h) is carried out by extending each further sub-set obtained in step e) which is at the top of the corresponding extended sub-set sorted in step d) by adding at the bottom thereof at least one reference vector corresponding to the reference vector that, in the corresponding sorted extended sub-set, is immediately below such top further subset.

9. The method according to claim 7, wherein step h) is carried out by extending each further sub-set obtained in step e) which is at the bottom of the corresponding extended sub-set sorted in step d) by adding at the top thereof at least one reference vector corresponding to the reference vector that, in the corresponding sorted extended sub-set, is immediately above such bottom further sub-set.

10. The method according to claim 7, wherein step h) is carried out by extending any other central further sub-set obtained in step e) by adding at the top and at the bottom thereof at least one reference vector corresponding to the reference vector that, in the corresponding extended sub-set sorted in step d), is immediately above and below such central further sub-set.

11. A non-transitory computer readable medium encoded with a computer program comprising program instructions to carry out the steps of the method according to claim 1, when the program is executed on an electronic processing system.

21. A device suitable for data compression comprising:

a feature extraction unit for processing a digital input data so as to provide Q-feature vectors, wherein Q is an integer higher than 1;

a memory unit for storing at least one vector codebook;

a data compression unit for identifying, for each input Q-feature vector provided by the feature extraction unit, a reference vector which is in the vector codebook stored in the memory unit that provides the lowest distortion with respect to the input feature vector; and

a codebook processing unit to carry out the steps of the method of claim 1.

12. A method, implemented by a computer, for compressing data, said data being represented by an input vector having Q features, wherein Q is an integer higher than 1, comprising the steps of:

1) providing a vector codebook, as generated by a method for generating a vector codebook providing low data compression computational effort starting from a vector codebook comprising a set of N reference vectors each comprising Q features, wherein N and Q are positive integers higher than 1, comprising the steps of;

a) sorting, by the computer, the set of N reference vectors in ascending or descending order with respect to values associated with a predetermined feature of the set of N reference vectors;

b) subdividing, by the computer, the set of sorted reference vectors in sub-sets;

c) associating, by the computer, with each of said sub-sets a respective threshold value for the predetermined feature;

d) sorting, by the computer, the reference vectors of each of said sub-sets in ascending or descending order with respect to values associated with a further predetermined feature of the set of N reference vectors;

e) subdividing, by the computer, each of said sub-sets of sorted reference vectors in further sub-sets;

f) associating, by the computer, with each of said further sub-sets a respective further threshold value for the further predetermined feature; and

g) extending at least one of the sub-sets obtained in step b) with at least one reference vector of an adjacent sub-set,

wherein steps d) and e) being carried out on the sub-sets extended according to step g),

wherein the set of N reference vectors sorted in step a) are arranged in a table form including N rows and Q columns, each row representing a reference vector having Q features;

2) identifying, by the computer, a sub-set of reference vectors among said sub-sets by progressively comparing a value of a feature of the input vector, which corresponds to said predetermined feature, with the threshold values associated with said sub-sets; and

3) identifying, by the computer, the reference vector which, within the sub-set identified in step

     2) provides the lowest distortion with respect to the input vector.

13. The method according to claim 12, wherein step 3) is carried out by identifying the reference vector which has a minimum distance from the input vector.

14. The method according to claim 12, further comprising a step of associating the index of the reference vector identified in step 3) with the input vector.

15. The method according to claim 12, further comprising the step of:

4) identifying, by the computer, a further sub-set, among the further sub-sets corresponding to the sub-set identified in step

     2), by progressively comparing the value of a further feature of the input vector, corresponding to said further predetermined feature, with the further threshold values associated with said further sub-sets, step

     3) being performed within the further sub-set identified in step

     4).

16. The method according to claim 15, wherein, the step 1) also comprises:

h) extending at least one of the further sub-sets obtained in step e) with at least one reference vector of an adjacent further sub-set to obtain extended further sub-sets, and steps

     4) and

     3) being performed on the extended further sub-sets.

17. A non-transitory computer readable medium encoded with a computer program comprising program instructions to carry out the steps of the method according to claim 12, when the program is executed on an electronic processing system.

18. A device suitable for data compression comprising:

a feature extraction unit for processing a digital input data so as to provide Q-feature vectors, wherein Q is an integer higher than 1;

a memory unit for storing at least one vector codebook; and

a data compression unit configured to carry out the steps of the method according to claim 12.

19. The device according to claim 18, wherein the data compression unit is also configured to associate the index of the reference vector providing the lowest distortion with the input Q-feature vector.

20. The device according to claim 18, further comprising a conversion unit for converting an input speech signal into digital speech data and to provide it to the feature extraction unit.

22. A distributed speech recognition system comprising:

a user device suitable for data compression comprising;

a feature extraction unit for processing a digital input data so as to provide Q-feature vectors, wherein Q is an integer higher than 1;

a memory unit for storing at least one vector codebook;

a data compression unit for identifying, for each input Q-feature vector provided by the feature extraction unit, a reference vector which is in the vector codebook stored in the memory unit that provides the lowest distortion with respect to the input feature vector;

a codebook processing unit to carry out the steps of method for generating said at least one vector codebook providing low data compression computational effort starting from a vector codebook comprising a set of N reference vectors each comprising Q features, wherein N and Q are positive integers higher than 1, comprising the steps of;

a) sorting the set of N reference vectors in ascending or descending order with respect to the values of a predetermined feature of the set of N reference vectors;

b) subdividing the set of sorted reference vectors in sub-sets;

c) associating with each of said sub-sets a respective threshold value for the predetermined feature;

d) sorting the reference vectors of each of said sub-sets in ascending or descending order with respect to values associated with a further predetermined feature of the set of N reference vectors;

e) subdividing each of said sub-sets of sorted reference vectors in further sub-sets;

f) associating with each of said further sub-sets a respective further threshold value for the further predetermined feature; and

g) extending at least one of the sub-sets obtained in step b) with at least one reference vector of an adjacent sub-set,

wherein steps d) and e) being carried out on the sub-sets extended according to step g),

and to store the generated vector codebook in the memory unit;

a recognition device for reconstructing and/or recognizing the digital input data; and

a transmission channel for data transmission between the user device and the recognition device.

23. The distributed speech recognition system according to claim 22, wherein the user device is adapted configured to transmit to the recognition device the indexes of the reference vectors providing the lowest distortion with the input Q-feature vectors.