RU2435214C2 - Method for fast search in codebook with vector quantisation - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: projections are constructed for each axis interval j-1 only for those Voronoy polygons whose projection intervals partially or completely overlap with the interval under investigation. Search is performed in form of transfers on tree branches. Successively for all axes, an interval is determined, in which the input vector component falls, and the last interval determines a hyper-rectangular cell with the final set of candidate vectors. The transfer route determines the input vector, and the terminal node determines he final set of code candidate vectors.

EFFECT: reduced capacity of the required storage devices and reduced consumption of computing resources when performing fast search in a codebook with vector quantisation.

4 dwg

Description

The invention relates to the field of radio engineering, and in particular to methods of encoding decoding and code conversion.

Vector quantization requires a sufficiently large number of operations during implementation, which leads to high computational complexity of this procedure as a whole; its reduction is an urgent task, especially for large volumes of processed information.

Known methods of vector quantization for the implementation of the coding of speech [Makhol D., Rukos S., Guiche G. Vector quantization in speech coding. // TIIER. - 1985. - T.73. - No. 11. - S. 19-61]. Also known is a method of searching in depth by an algebraic cipher book [RU 2175454 C2 10.27.2001]. It offers a search for some tree structure with a given number of levels. It uses probabilistic methods to carry out the search procedure, which can lead to an incorrect choice of the code vector, and this approach is also characterized by greater computational complexity compared to the method presented in [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]. The method described in the article is also characterized by rather greater computational complexity.

The closest in technical essence to the claimed method is the method of quick search for the closest vector in the codebook, which is characterized by lower computational complexity compared to existing analogues, a description of which is presented in [DYCheng, A.Gersho, B. Ramamurthi, and Y.Shoham, "Fast search algorithms for vector quantization and pattern matching," in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, Mar. 1984, vol. 1, pp. 9.11.1-9.11.4]. The main disadvantage of the prototype is the exponential growth of memory with increasing dimensionality of space. The amount of required memory is described by the expression (2N-1) ^K γ, where γ is the average size of memory required to store the final set of candidate vectors, N is the total number of code vectors, and K is the dimension of space. The technical implementation of the method is associated with difficulties in memory growth, for example, for 32 vectors in 10-dimensional space, with a value of γ equal to two bytes, 2 ⁴⁸ bytes are needed.

, таких что

, при этом границы разбивают j-ю координатную ось на (2N-1) последовательных интервала {I^j(1),I^j(2), … I^j(2N-1)}, где

, m - номер интервала, причем каждому интервалу соответствует набор индексов многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I^j(m), а набор кодовых векторов кандидатов связывают с каждой из гиперпрямоугольных ячеек, полученных в процессе предварительной обработки и хранящихся в некоторой таблице, что и выбирают итоговым набором векторов кандидатов, на этом малом наборе далее проводят поиск, при котором для каждого компонента входного вектора определяют интервал, в который попадает данный компонент. Причем гиперпрямоугольники получаются при выполнении описанной операции построения проекций на все оси.The method described in the prototype is that K-dimensional space is divided into hyper-rectangular cells by constructing projections of the Voronoi polygon for each code vector on the coordinate axis j, j = 1, forming N overlapping projection intervals that form 2N projection boundaries

such that

, while the boundaries divide the j-th coordinate axis into (2N-1) consecutive intervals {I ^j (1), I ^j (2), ... I ^j (2N-1)}, where

, m is the number of the interval, and each interval corresponds to a set of indices of Voronoi polygons whose projection intervals partially or completely overlap with I ^j (m), and the set of candidate code vectors is associated with each of the hyper-rectangular cells obtained during the preliminary processing and stored in some the table, which is chosen by the final set of candidate vectors, on this small set, a search is then carried out in which for each component of the input vector the interval into which this component falls . Moreover, hyper-rectangles are obtained by performing the described operation of constructing projections on all axes.

содержит все точки в пространстве R^K, наиболее близкие к

, чем к какому либо другому кодовому вектору. Таким образом, если кодовый вектор

находится в многоугольнике V_i, то связанный кодовый вектор

будет ближайшим.We describe the prototype in more detail. When it is implemented, information on the projections of Voronoi polygons is used, and the K-dimensional space is divided into (2N-1) ^K hyper-rectangular cells containing a set of resulting candidate code vectors. Voronoi polygon V _i associated with the codebook vector

contains all points in the space R ^K closest to

than to any other code vector. So if the code vector

is in the polygon V _i , then the associated code vector

will be the closest.

, с начальной и конечной точкой

. Данную процедуру построения проекций осуществляют для всех N многоугольников, получают N перекрывающих интервалов проекций многоугольников Вороного

, i=1, …, N, которые образуют 2N границ проекций

таких что

. Эти границы делят j-ю координатную ось на (2N-1) последовательных интервала {I^j(1),I^j(2), … I^j(2N-1)}, где

. Каждому интервалу ставят в соответствие набор S^j(m) индексов многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I^j(m).To build the structure on which the search will be organized, preprocessing is performed in the form of "dividing the space R ^K into hyper-rectangular cells". To do this, build the projection of the polygon V _i on the coordinate axis j (figure 1), get the interval

, with start and end point

. This procedure for constructing projections is carried out for all N polygons; N overlapping intervals of projections of Voronoi polygons are obtained

, i = 1, ..., N, which form 2N projection boundaries

such that

. These boundaries divide the jth coordinate axis into (2N-1) consecutive intervals {I ^j (1), I ^j (2), ... I ^j (2N-1)}, where

. Each interval is assigned a set of S ^j (m) indices of Voronoi polygons whose projection intervals partially or completely overlap with I ^j (m).

. Эту операцию разделения на интервалы повторяют для всех К осей. Далее определяют гиперпрямоугольную ячейку по формуле (1)The set of indices S ^j (m _j ) associated with the interval I ^j (m _j ) determines the candidate code vectors that may be closest to the input vector

. This intervaling operation is repeated for all K axes. Next, determine the hyper-rectangular cell according to the formula (1)

, который получают по формуле (2):Each cell is associated with a final set of candidate code vectors

, which is obtained by the formula (2):

A set of candidate code vectors associated with each of the (2N-1) ^K hyper-rectangular cells obtained during the preprocessing is stored in a table.

определяют интервал, в который она попадает

, т.е. компонент вектора x_j удовлетворяет условию

, далее для всех К осей формируют интервалы I^j(m_j), j=1, …, K, содержащие компоненты вектора

. Далее определяют гиперпрямоугольную ячейку, в которой лежит входной вектор

, по формуле (1), затем с таблицы считывают соответствующий ей набор кодовых векторов кандидатов.The search is as follows. For each component of the input vector

determine the interval in which it falls

, i.e. the component of the vector x _j satisfies the condition

, then for all K axes form intervals I ^j (m _j ), j = 1, ..., K, containing the components of the vector

. Next, determine the hyper-rectangular cell in which the input vector lies

according to formula (1), then the corresponding set of candidate code vectors is read from the table.

On this small set, a search is then carried out using the exhaustive search method. This procedure requires all Klog (2N) comparisons to find the final set. However, the disadvantage of the prototype is the large amount of memory required to store the table (2N-1) ^K γ, as well as a fairly high computational complexity.

The aim of the invention is to provide a quick search method in the codebook for vector quantization with computational complexity and the required memory capacity lower than that obtained in the prototype.

The technical result of the proposed method is to reduce the required amount of memory devices and computational complexity when searching in the codebook with vector quantization.

The technical result is achieved by the fact that in the method of searching in the codebook for vector quantization used in the prototype, when constructing projections of the Voronoi polygons on the coordinate axis j, j ≠ 1, projections for each interval of the j-1 axis are constructed only of those Voronoi polygons that are included in the set of indices for this interval, i.e. for those whose projection intervals partially or completely overlap with the considered interval, then at the search stage the interval into which the input vector component falls is determined sequentially for all axes, and the last interval defines a hyper-rectangular cell with the final set of candidate vectors.

, i=1, …, N, которые образуют 2N границ проекций

таких что

. Эти границы разделяют рассматриваемую координатную ось на (2N-1) последовательных интервалов {I¹(1), I¹(2), … I¹(2N-1)}, где

. Каждый интервал соответствует набору S¹(m) индексов многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I¹(m). Далее для каждого интервала I¹(m) m=1…(2N-1) на следующую рассматриваемую ось строят только проекции многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I¹(m), т.е. входящих в набор S¹(m). Получают N₁<N перекрывающих интервалов проекций

, i=1, …, N₁, где N₁ - определяется количеством векторов, входящих в набор S¹(m). В итоге получают 2N₁ границ проекций

таких, что

. Эти границы разделяют рассматриваемую координатную ось на (2N₁-1) последовательных интервалов {I²(1), I²(2), … I²(2N₁-1)}, где

. Каждому интервалу соответствует набор S²(m) индексов многоугольников Вороного, чьи интервалы проекций частично или полностью перекрываются с I²(m) и входят в набор S¹(m).Consider the claimed method in more detail. The projections of all N Voronoi polygons V _i are built on the first of the axes under consideration. Get N overlapping projection intervals,

, i = 1, ..., N, which form 2N projection boundaries

such that

. These boundaries divide the coordinate axis in question into (2N-1) consecutive intervals {I ¹ (1), I ¹ (2), ... I ¹ (2N-1)}, where

. Each interval corresponds to a set of S ¹ (m) indices of Voronoi polygons whose projection intervals partially or completely overlap with I ¹ (m). Further, for each interval I ¹ (m) m = 1 ... (2N-1), only the projections of Voronoi polygons, whose projection intervals partially or completely overlap with I ¹ (m), are constructed on the next axis under consideration. included in the set S ¹ (m). Get N ₁ <N overlapping projection intervals

, i = 1, ..., N ₁ , where N ₁ - is determined by the number of vectors included in the set S ¹ (m). As a result, 2N ₁ projection boundaries are obtained

such that

. These boundaries divide the coordinate axis in question into (2N ₁ -1) consecutive intervals {I ² (1), I ² (2), ... I ² (2N ₁ -1)}, where

. Each interval corresponds to a set of S ² (m) indices of Voronoi polygons, whose projection intervals partially or completely overlap with I ² (m) and are included in the set S ¹ (m).

The procedure is repeated for each interval I ² (m), m = 1 ... (2N ₁ -1) and only the projections of Voronoi polygons from the set S ² (m) are built on the next axis. So all K axes are sequentially considered. As a result, a data structure for the search in the form of a tree is obtained, as shown in FIG.

попадает в интервал

, если компонент вектора

. На следующем этапе рассматривают поддерево, порожденное узлом I¹(m) (фиг.2), таким образом, анализируют каждый компонент входного вектора, на последнем этапе интервал I^K(m), в который попадает компонент x_K, определяет концевой узел, который определяет итоговый набор С^'(х).The search is implemented as transitions on tree branches. So the input vector

falls into the interval

if the component of the vector

. At the next stage, the subtree generated by the node I ¹ (m) is considered (Fig. 2), thus, each component of the input vector is analyzed, at the last stage, the interval I ^K (m), into which the component x _K falls, determines the end node, which defines the final set C ^' (x).

Thanks to the new set of essential features of the quick search method in the codebook during vector quantization due to the successive elimination of Voronoi polygons when constructing projections on the axis, it is possible to reduce the number of storage devices and reduce the cost of computing resources when performing a quick search in the code book during vector quantization.

The analysis of the prior art made it possible to establish that analogues that are characterized by a set of features identical to all the features of the claimed technical solution are absent, which indicates the compliance of the claimed device with the patentability condition of "novelty".

Search results for known solutions in this and related fields of technology in order to identify features that match the distinctive features of the claimed object from the prototype showed that they do not follow explicitly from the prior art. The prior art also did not reveal the popularity of the impact provided by the essential features of the claimed invention, the transformations on the achievement of the specified technical result. Therefore, the claimed invention meets the condition of patentability "inventive step".

The claimed technical solution is illustrated by drawings, which show:

figure 1 is a Voronoi diagram for sixteen points on a plane, the Voronoi polygon is highlighted in bold lines;

figure 2 - illustration of the data structure for the search in the form of a tree;

figure 3 is a functional diagram of a procedure for generating a data structure and an indexed table of candidate vectors;

4 is a functional diagram of the implementation of the search procedure for the nearest code vector.

A functional diagram of the implementation of the procedure for generating a data structure and an indexed table of candidate vectors is shown in FIG. 3. It consists of a Voronoi diagram block 1, which receives a set of code vectors, the output of block 1 is connected to the input of the Voronoi polygon projection block 2, the input of which is a set of Voronoi polygons along the y axis, the output of block 2 is connected to the input of the point ordering block 3 projections of Voronoi polygons along the y axis, to the input of which projections of polygons from block 2 are received, the outputs of block 3 are connected to the inputs of block 4 for determining the intersection of Voronoi polygons with the obtained intervals orye input to block 4 block 3, the output of unit 4 is connected to the input unit 2 and unit 5 creating an indexed table candidate vectors at the input of which receives the Voronoi polygons. The output of block 5 is a set of resulting code vectors.

Consider the implementation of the procedure for generating a data structure and an indexed table of candidate vectors. Block 1 receives information about the codebook vectors, block 1 constructs the Voronoi diagram and generates at the output a set of Voronoi polygons corresponding to the code vectors, the information about which is fed to block 2, which forms the projections of each polygon on the axis, then they are fed to the input of the block 3, which arranges the projection points along the axis and forms a set of intervals, which is fed to block 4. Block 4 for each obtained interval defines a set of polygons whose projection coordinates intersect the given th interval, and in the initial set for the determination includes only those polygons, which formed this set of intervals. At the output of block 4, information on a set of Voronoi polygons for each interval is generated. If the set of intervals was built for the last of the considered axes, then the resulting set of polygons is the final one, if not, then information about the set of polygons is fed to block 2.

Figure 4 shows a functional diagram of the procedure for finding the nearest code vector. It consists of a block 101 for determining the interval for which the components of the code vector arrive sequentially, the output of block 101 is connected to the input of the block for determining the cell of the table of finite vectors, to which the last determined interval arrives, the output of block 102 is connected to the input of the block 103 for reading from the table, the output block 103 is connected to the input of block 104 for storing the table of final sets of code vectors, and the output of block 104 is connected to the input of block 103, and the output of block 103 is the final set of candidate code vectors. Its functioning is as follows. Block 101 sequentially receives the components of the code vector. For each component, block 101 sequentially determines at what interval it falls, thus, a transition occurs along the nodes of the tree (see figure 2). The last determined interval is supplied to the block determining the cell of the finite vector table, where the cell of the finite vector table is determined from this interval. The index of a specific cell is supplied to a table reading unit 103, which at this index reads from the table storage unit 104 of the table of final sets of code vectors, as a result, at the output of block 103, the final set of candidate code vectors.

The advantages of the method include the fact that the construction of the projections of Voronoi polygons is carried out sequentially on each of the measurement axes and subsequently for each interval only projections of those polygons whose projections intersect this interval are built. Application of the proposed approach allows you to organize the structure for the search in the form of a tree. The end node of which uniquely determines the final set of candidate vectors.

Industrial application of the method is due to the presence of the element base, on the basis of which devices that implement this method can be made. The application of the proposed method will significantly reduce the amount of storage devices required for implementation in comparison with the prototype, and the implementation of the transition procedure through the tree nodes will reduce the amount of computational cost.

The computational complexity of the proposed method Z _n for finding a single vector is found using the following expression:

where N _i varies, N _i = N ... N _K , N ... N _K is the number of vectors of applicants that remained not excluded after considering the ith axis, S is the final number in C '(x) of the final set of candidate vectors, and δ is the number of operations to calculate the distance to the code vector. For comparison, the computational complexity Z proposed in the prototype:

From expressions (3) and (4) we obtain the expression for the obtained effect with respect to computational complexity:

The amount of memory required to implement the prototype is estimated by the expression:

where γ is the average size of memory required to store the final set of candidate vectors.

Assessment of the used memory of the proposed method M _n is equal to:

From expressions (6) and (7) we obtain the expression for the obtained effect on the use of memory:

Consider an example that demonstrates the effectiveness of the proposed method in relation to the prototype for the case of 32 vectors for four-dimensional space (N = 32, K = 4), in terms of computational complexity and the use of memory resources. By computing resources for the prototype:

Z = d · log ₂ · 2 · N + δ · S = 4 · 6 + δ · S = 24 + δ · S,

for the proposed method:

We get the gain in computational complexity:

E _z = (Z / Z _n ) = 2.18, i.e., to encode one input vector with a vector from the codebook, the developed method requires an average of 2.18 times less operations than the method described in the prototype.

By using memory resources

M = (2N-1) ^K γ = (2 · 32-1) ⁴ γ = 15752961 · γ

We get the gain in computational complexity:

Get the gain on the use of memory resources:

Claims (1)

A quick search method in the codebook for vector quantization, namely, that the K-dimensional space is divided into hyper-rectangular cells by constructing projections of the Voronoi polygon for each code vector on the coordinate axis j, j = l, forming N overlapping projection intervals that form 2N projection boundaries (

,

, ...,

) such that (

≤

≤ ... ≤

), while the boundaries divide the jth coordinate axis into (2N-1) consecutive intervals {I ^j (1), I ^j (2), ..., I ^j (2N-1)}, where I ^j (m) = {(

,

)}, m is the number of the interval, and each interval corresponds to a set of indices of Voronoi polygons whose projection intervals partially or completely overlap with I ^j (m), and a set of candidate code vectors is associated with each of the hyper-rectangular cells obtained during pre-processing and stored in some table, which is chosen by the final set of candidate vectors, on this small set, a search is then carried out in which for each component of the input vector the interval into which this component falls m, characterized in that in the method of searching in the codebook for vector quantization used in the prototype, when constructing projections of the Voronoi polygons on the coordinate axis j, j ≠ 1, projections for each interval of the j-1 axis only of those Voronoi polygons that are included into the set of indices of this interval, i.e. for those whose projection intervals partially or completely overlap with the considered interval, then at the search stage the interval into which the input vector component falls is determined sequentially for all axes, and the last interval defines a hyper-rectangular cell with the final set of candidate vectors.

Images