Method of creating codebook and search therein during vector quantisation of data. RU patent 2504027.

FIELD: information technology.

SUBSTANCE: method can be used to reduce consumption of computational resources and the required size of storage devices when creating codebooks and executing reference vector search algorithms therein, including when performing low-speed speech signal coding. The technical result of the disclosed method is reducing the required size of storage devices and reducing consumption of computing computational resources when performing search in a codebook during vector quantisation. The set task is achieved by constructing a special codebook structure based on neural networks using training algorithms with adjustment. Search is performed in form of step-by-step hierarchical vector quantisation. The resultant vector is a sum of code vectors found at each step. The disclosed method can be used to reduce consumption of computational resources and the required size of storage devices when executing reference vector search algorithms in a codebook.

EFFECT: reducing consumption of computational resources and the required size of storage devices.

7 dwg

The invention relates to the field of digital communication, namely, the methods of reducing the amount of data during their processing. The proposed method can be used to reduce the cost of computing resources and the required volume of storage devices when creating code books and realization of algorithms of search of support vectors in them, including in the implementation of low-rate coding of speech signals.

Vector quantization requires a sufficiently large number of operations with the formation of the code books and search vectors in them, which leads to high computational complexity of these procedures, especially with large volumes of the processed information. Reduction of the number of computational operations when looking for a vector in the code book is an urgent task.

Known methods of vector quantization for the procedure of coding of speech [Makhoul D., C., Gish, Vector quantization in coding of speech. // . - 1985. - .73. - №11. - P.19-61], [V. Ramasubramanian and Kuldip K. Paliwal «Fast Nearest-Neighbor Search Based on Voronoi Projections and Its Application to Vector Quantization Encoding» in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, vol. 1, no. 2, March 1999]. Also known way to create code book and depth first search, presented in the patent RU 2175454 C2, which proposes a tree structure with a preset number of levels. This method is characterized by a greater computational complexity, since it uses probabilistic methods for implementing the procedure of finding the support vector-centroid of each cell in the code book. In the patent RU 2391715 C2 describes the principle of multidimensional vector quantization using multi level code books. The disadvantage of this method are the requirements for the availability of relatively large amount of memory needed to store the tables coordinates support vector machine centroids.

The closest to the technical nature of the claimed method is a method referred to in the patent US 6161086, where the vector quantization of the data in a linear prediction speech signal signal conditioning excitation synthesizing filter use the combined code book composed of a fixed and adaptive code books, and adaptive correction code book produced with the help of the inverse procedure BIFT (Backward and Inverse Filtered Target) on three levels adaptive code book. Fixed code book contains a stochastic component of the excitation signal, which displays component. Adaptive code book is formed on the basis of the tonal component of excitation signal and shows the availability of long-term correlations due to structure of the speech signal and carries information on the number of readings of the corresponding period of the main tone of the analyzed frame speech.

Finding support vector machine is using a tree structure, find the nearest vector in the code book, which requires high computational complexity.

The disadvantage of the prototype is the large amount of memory needed to store the table of coordinates of support vectors, as well as the high computational complexity of this operation.

The objective of the invention is to create a code book and search in it when vector quantization, allowing to reduce the amount of storage devices and the computational complexity of implementing the procedure of search in the code book.

This task is solved by the fact that when creating the code book and search in it when vector quantization in the combined code book for fixed codebook used self-learning neural network Kohonen, also known as card self - SOM (self-organizing ball), and for adaptive code book apply neural network with quantization - LVQ (learning vector quantization). A procedure of finding implement fully hierarchical vector quantization, which provides small loss of accuracy while increasing the speed of calculations.

Consider the claimed method more. Neural network SOM is intended for transformation of received vectors signals with arbitrary dimension, in one - or two-dimensional discrete map. In this case, such a transformation is performed adaptively in topologically consistent manner. Figure 1 shows the schematic diagram of the two-dimensional lattice of neurons used as a discrete card for the functioning of fixed codebook. All the neurons of the lattice connected to all the nodes in the input layer. This network has the structure of direct distribution with one computing layer composed of neurons that are arranged in columns and rows.

The essence of self-learning neural network SOM consists in the formation of the card (space) coordinates of vectors with the division into cell (Voronoi polygons)with support vector-centroid of each polygon. The essential characteristics of the algorithm of self-learning, necessary for the formation of fixed codebook, are:

continuous input image space activation (stochastic vectors excitation signals), which is generated according to some probability distribution;

- the topology of the neural networks in the form of a grid consisting of neurons, defining a discrete output space;

- the time-dependent function surroundings h j,i(x) (n), which determines the radius of the surroundings neuron-winner of i(x);

- the speed parameter training η(n), for which to set the initial value η 0 and which is gradually decreasing in time n, but never reaches zero.

It is experimentally established that the formation of fixed code book value η(n)equal to 0.005, it is necessary for a proper statistical accuracy during convergence. However, to create a codebook was used signal balance of long-term linear prediction speech from the output filter synthesis. Description of the linear prediction speech fairly presented in detail in (SERGEY Bykov, V.I. Zhuravlev, Shalimov I.A. Digital telephony: Textbook. manual for high schools. - M: Radio and communication, 2003. - Pp. 102-105).

The sequence of steps prior training in fixed code book next.

1) Initialization. For source vectors of synaptic weights of the neural network w j (0) take a random values from the set of input vectors

. As a condition of correct training on vectors of excitation filter synthesizing of speech signals, you must difference vectors for different values of j=1,2,...,l, where l is the total number of neurons in the lattice.

2) Subsampling. Choose the vector x of the input space with a certain probability. This vector is an institution, which is applied to the lattice of neurons. The dimension of the vector x: is m.

3) Search of maximum likelihood. To find the most suitable (who) neuron i(x) at step n, using the criterion of minimum Euclidean distance:

4) Correction. Correction vectors of synaptic weights of all neurons

w j (n+1)=w j (n)+η(n)h j,i(x) (n)(x-w j (n)),

where η(n) - the speed parameter learning; (h j,i(x) (n) is the function of the neighborhood with the center in conquered the neuron i(x). Both of these parameters dynamically change during training to obtain the best result.

5) Continued. Return to step 2 and calculation to achieve a given number of iterations.

Upon completion of the process of convergence of the self-organizing map (SOM) displays important statistical characteristics of the space of stochastic vectors excitation signals. Because the algorithm SOM refers to the algorithms of training of neural networks «without a teacher», formed by the space of Voronoi cells is close in terms of placement support vector machine centroids in the N-dimensional coordinate system. The approximation is determined by the vectors of synaptic weights of neurons on the map features.

As a mechanism for fine-tuning is necessary to make quantization vectors training. For the quantization of the vector-centroid is used method of training «teacher»that uses the class information for small-displacement support vector and, accordingly, the Voronoi cell borders and, consequently, to improve the quality of regions of the decision of the classifier. If the label class input vector x and vector-centroid (vector Voronoi) w consistent, then the latter is shifted towards the first. When vector-centroid moves in the direction opposite to the vector x. Briefly the process of quantization is described as follows:

1) in the case of the maximum proximity of vector Voronoi w C to input vector x i w C (n+1)=w (C (n)+a n [x i w C (n)], where 0<α n <1;

2) if there is a mismatch w C (n+1)=w (C (n)-a n [x i w C (n)];

3) other vectors the Voronoi not changed.

Constant training α n for the formation of fixed codebook choose monotonously decreasing with an initial value of 0.05. As a result of the adaptation procedure after a few passes over the data input the coordinates of support vector Voronoi stops scrolling, and consequently, and the creation of a space Voronoi polygons for fixed codebook stochastic component signals excitation.

For adaptive code book offered to use the neural network LVQ. Figure 2 presents the structure of the neural network that functions as a code book, which stores information about the space of Voronoi cells with vectors tone component of excitation signal. In the case of speech signal processing network LVQ is a cascade connection layer SOM and network. Self-organizing layer captures significant signs of process (localizes them based on the input), after which they attributed to the input vector in layer. Because of good localization signs process tone excitation of the first layer of the network in most applications, speech processing suffice application perceptron, containing only one layer of neurons (often linear).

LVQ network is taught on the basis of the set of pairs of input/output, composed of elements of the training sequence {R,T}: {p-1 , t 1 },{p-2 , t 2 },...,{P Q t Q }. Each target vector has the only element equal to 1, and the rest are equal to 0. For the network training determine the vector of input p, such that in a competing layer configured the elements of the matrix of weights W 1.1 . Weights neuron i* most similar to the input vector p and the neuron i* wins the competition. Then competing activation function returns 1 as the item i* vector and 1 , and all other elements and 1 is equal to 0. In the second, layer work W 2.1 *a 1 highlights some column of the matrix W 2.1 and an associated class of k*. Thus, the network connects the input vector p class k*. This destination can be either correct or wrong. Therefore, in the process of training you need to edit a line i* matrix W 1.1 thus, to bring it closer to the vector p, assignment of the right, and remove from the vector p, if the destination is incorrect. Based on this, a rule setting the following parameters:

As a mechanism for fine-tuning produce quantization vectors learning similarly correction fixed codebook. It is experimentally established, that for the formation of adaptive code book monotonically decreasing constant training α n is equal to 0.07.

Flowchart algorithms of fixed and adaptive code books are presented in figure 3 and figure 4.

When performing a search procedure is used multi-stage hierarchical vector quantization, which accelerates the speed of the search unlike the tree search support vector-centroid. Multilevel hierarchical vector quantization shares a common search operation on a lot of sub-operations, each of which requires a small amount of calculations for fixed and adaptive code book. In each sub-operation process the remainder of the vector, formed in the previous . Input vector quantizing Li - tier vector quantizer, the remainder (error) quantization fed to the input of the second Lj - tier vector quantizer. The process can be repeated any number of sub-stages.

The final quantized vector value for both code books are in the form of the sum of output vectors of intermediate and final .

The analysis of the equipment has allowed to establish that the analogues, characterized by the totality of features identical to all features of the claimed technical solutions, no, that indicates compliance of the claimed device with the condition of patentability "novelty".

Search results known solutions in this and related areas of technology for signs that coincide with the distinctive features of the prototype of the declared object, showed that they are obvious from the prior art. Of the level of technology also found no known impact involves the essential features of the claimed invention transformations to achieve the specified result. Therefore, the claimed invention meets the condition of patentability of "inventive step".

Industrial applicability of the invention by the fact that it can be done with the help of modern element base, with the achievement of specified in the invention of destination.

For fixed codebook it consists of the creation of initial data vectors training stochastic component signals excitation 1, the output of the unit 1 is connected with the entrance of the block of preliminary training of a neural network SOM 2, the output of the unit 2 connected to the input of correction block support vector machine centroids 3, block 3, connected to the input of the block storage indexed in the vector table 4 candidates.

Functional scheme of the procedure for formation of fixed codebook and indexed tables vectors of candidates is shown in figure 5.

For adaptive code book schema contains the set of initial data vectors training tone component signals excitation 5, the output of the unit 5 is connected to the entrance of the block of the first level of adaptation of the neural network LVQ 6, block 6 is connected to the entrance of the block of the second level of adaptation of the neural network LVQ 7, exit block 7 connected to the input of correction block support vector machine centroids 8, the output of the unit 8 is connected with the entrance of the block storage indexed in the vector table 9 candidates.

Functional diagram of the implementation of the procedure of the formation of adaptive code book and indexed tables vectors of candidates is shown in Fig.6.

Box 1 contains information about the source data for neural network training SOM is the vectors excitation for synthesizers speech signals containing stochastic (noise) components. Data vectors to the input unit 2 of the preliminary training of a neural network SOM fixed code book, in block 2 of the procedure is performed, the settings of weight coefficients specified neural network, thereby creating space Voronoi cells with vectors-centroids, with an output of unit 2 information to the input of the unit 3, where there is a correction of support vectors according to description of the mechanism of fine-tuning (P.5), with an output of unit 3 unit 4 are submitted data about the coordinates of the Voronoi cells and vectors candidates for their storage in the form of a table which represents the fixed code book.

Box 5 contains information about the source data for neural network training LVQ is vectors excitation for synthesizers speech signals containing tone () components. For teaching two-level neural network LVQ adaptive code book vectors excitation served with an output of unit 5 unit 6, where there is a setting weights of the first layer of the network LVQ, according to the algorithm of learning without a teacher», similar to the algorithm of training SOM. From the output of the block 6 block 7 of the second layer of a neural network LVQ served previously created the coordinates of the cell and vectors Voronoi, which is the completion of the adaptation procedure using a learning algorithm with a «teacher»as the second level of adaptation is layer neural network LVQ. With an output of unit 7 information to the input of the unit 8, where there is a correction of support vectors according to the mechanism of fine-tuning (P.5), with an output of unit 8 in block 9 move the data on the coordinates of Voronoi cells and vectors candidates for their storage in the form of a table which represents the adaptive code book.

Block diagram of the algorithm for the multi-stage hierarchical vector quantization performing the procedure for search in fixed and adaptive code books, presents the Fig.7.

Application of the proposed method will substantially reduce required for the implementation of the volume of the storage devices on 25-30%and the realization process of the multi-stage hierarchical vector quantization reduce computational costs on 20-23% in comparison with the known solutions in this sphere.

Way to create code book and search in it when vector quantization of the data, according to which to obtain the excitation signal synthesizing the filter at a linear prediction speech signal uses a code book composed of a fixed and adaptive code books

wherein the to create a fixed codebook form the original data vectors training stochastic component signals excitation, train the neural network Kohonen SOM (self-organizing map), for self-learning algorithm which determines the continuous input image space activation of stochastic vectors excitation signals generated according to some probability distribution, then form the topology of the neural networks in the form of a grid consisting of neurons and defining the discrete output space, then calculate the time-dependent function surroundings h

(n) to find the radius of the surroundings neuron-winner and gradually decreasing in time, but never reaches zero parameter speed training η(n) with initial value η 0 , then adjust the support vectors centroid for storage index table of vectors of candidates, and to create an adaptive code book form the original data vectors training tone component signals excitation, produce a two-level adaptation neural network with quantization of the LVQ (learning vector quantization), correct the reference vectors centroid for storage index table vectors of candidates, the procedure of search in the code books implement with the use of multi-stage hierarchical vector quantization.