RU2595598C2 - Method and device for compression using approach based on neural network - Google Patents

Abstract

FIELD: computer engineering.

SUBSTANCE: method of compressing data using approach based on neural network consisting of training mode and output mode in which input data space is divided into multiple data elements, wherein each data element is characterised by coordinate vector and vector of 3D values; using coordinate vectors, determined address cells in content addressable memory with which must be related data elements, wherein each of cells has weight value; data elements associated with cells in content addressable memory based on certain addresses; accumulated all weight cell values associated with data elements to obtain weight vector; weight vector is subtracted from volume vector values to generate error signal; and if error signal is non-zero, include training mode, wherein weight cell values associated with data elements, controlled based on error signal; or if error signal is zero, include output mode, where vector compressed volume values is calculated using weighting vector and then discharged.

EFFECT: reduced expenses of memory and computational costs for data compression.

6 cl, 4 dwg

Description

FIELD OF THE INVENTION

The present invention relates generally to the field of data processing technology. In particular, the present invention is directed to a method and apparatus for compressing data using a neural network approach.

State of the art

Compression and storage of bulk data are characteristic of systems used for 3D modeling, machine pattern recognition and robotic applications. Three basic approaches are known in the art for compressing and storing bulk data: 1) voxel representation in linear memory (RAM, flash memory, etc.); 2) lossless data compression using hierarchical data structures; and 3) lossy data compression.

The voxel representation in linear memory is used when the computational efficiency of systems is important. In this case, the data is stored in memory without any modification, i.e. in its original form. A voxel is a single item or data point on a regularly spaced three-dimensional grid. This data point may consist of a single data component, such as opacity, or multiple data components, such as color, in addition to opacity. A voxel represents only one point on this grid, not a volume; the space between each voxel is not displayed in the voxel-based dataset. An example of a wax presentation is described in US Pat. No. 8,587,583 B2. The disadvantage of the voxel representation is that this approach requires large capacity storage devices in the case of a large amount of bulk data. In addition, a 3D view usually contains a lot of empty space, and a “straightforward” voxel view can be costly in terms of using memory resources.

To reduce the cost of memory resources, you can compress bulk data. For lossless data compression, various hierarchical data structures like the data tree are used. Empty spaces are encoded with much lower resolution than spaces with objects, and this reduces the required data size. The most used type of this approach is the octant tree - a data structure in which each internal node has exactly eight descendants. Each node in the octant tree divides the space that it characterizes into eight octants. An example of lossless data compression is described in US Pat. No. 4,694,404 A. This approach has such a drawback that presenting data using the octant tree requires additional computational cost for packing / unpacking the data.

Lossy data compression often leads to better compression ratios than lossless data compression, as some raw data may be discarded. To compress data with losses, either the dominant features of the source data or their compact representation in other bases are determined. The amount and type of discarded information is dictated by the selection metric in the compression algorithm. An example of a lossy data compression scheme is described in US 2013/0159263 A1. This document discloses a method involving a sparse representation of an input data vector b∈R ^m using an overflowed dictionary of basis vectors A∈R ^mxn . In particular, given the vocabulary matrix with m <n, it is of interest to find x∈R ⁿ so that Ax = b. There are many such solutions for x, and the principle is to choose the solution that is the most “sparse”. It should be noted that while x has a high dimension, A can be chosen so that x has very few nonzero elements, and therefore x can be stored in an efficient way. In document US 2013/0159263 A1, the distributed Bregman algorithm is used to solve the optimization problem of finding the most “sparse" solution for x. This approach also requires significant computational overhead for data processing, in particular for the implementation of the distributed algorithm according to Bregman.

Another way to find a solution for x is based on the neural network approach described in US 4,193,115 A. In this case, control functions are calculated for a variety of input variables, which are calculated in relation to the data stored in memory. Each value of the control functions is allocated to different physical memory addresses, so that a linear sum of the contents of these physical addresses determines this value. An addressing algorithm is used in which the input variables are mapped to a set of intermediate display values. A device for performing intermediate mapping contains the first and second counters, which are used to address memory that stores intermediate variables in a specified way. However, the solution proposed in US 4,193,115 A also requires significant computational overhead for data compression.

Disclosure of invention

An object of the present invention is to overcome the aforementioned disadvantages inherent in solutions known in the art.

The technical result achieved by using the present invention is to reduce memory and computing costs for data compression by using a neural network approach.

According to a first aspect, a method for compressing data is provided. The method is as follows. The input data space is divided into many data elements. Each data element is characterized by a coordinate vector defining the coordinates of the data element in the input data space, and a volume vector that defines the volume values of the data element in the input data space. Using coordinate vectors, they determine the addresses of cells in associative memory with which data elements should be associated. Each of the cells has a weight value. Next, data elements are associated with cells in associative memory based on specific addresses. All weight values of cells associated with data elements are accumulated to obtain a weight vector. After that, the weight vector is subtracted from the vector of volume values to generate an error signal. Then check whether the error signal is non-zero. If the error signal is nonzero, a training mode is activated in which an error signal is provided with an associative memory for adjusting cell weights associated with data items based on the error signal. If the error signal is zero, an output mode is activated in which a vector of compressed volume values is calculated using a weight vector and then output.

According to a second aspect, a data compression device is provided. The device comprises an associative memory consisting of cells and one or more processors. Each of the cells in associative memory has a weight value. Mentioned one or more processors are configured to divide the input data space into multiple data elements. Each data element is characterized by a coordinate vector defining the coordinates of the data element in the input data space, and a volume vector that defines the volume values of the data element in the input data space. Mentioned one or more processors are additionally configured to, using coordinate vectors, determine the addresses of cells in associative memory with which data elements should be associated, and associate data elements with cells in associative memory based on specific addresses. Mentioned one or more processors are additionally configured to accumulate all weight values of cells associated with data elements to obtain a weight vector and subtract the weight vector from the volume vector to generate an error signal. Said one or more processors is further configured to, if the error signal is nonzero, enable a learning mode in which the weight values of cells associated with data elements are adjusted based on the error signal, or if the error signal is zero, enable an output mode in which a vector of compressed volume values is calculated using a weight vector, and a vector of compressed volume values is output.

These and other aspects, features and advantages of the invention will be apparent and elucidated with reference to the embodiment (s) of implementation described (e) herein.

Brief Description of the Drawings

The essence of the present invention is explained below with reference to the accompanying drawings, in which:

FIG. 1 illustrates a data compression device in accordance with one example of an embodiment of the present invention;

FIG. 2 shows a three-dimensional representation of the associative memory shown in FIG. one;

FIG. 3 shows a data compression method in accordance with one example embodiment of the present invention;

FIG. 4 shows an example of the use of the method of FIG. 3 with respect to sinusoidal function.

The implementation of the invention

Various embodiments of the present invention are described in more detail below with reference to the accompanying drawings. However, the present invention can be implemented in many other forms and should not be construed as being limited by any particular structure or function described in the following description. On the contrary, these embodiments are provided in order to make the description of the present invention detailed and complete. Based on the present description, it will be obvious to a person skilled in the art that the scope of the present invention encompasses any embodiment of the present invention that is disclosed herein, regardless of whether this embodiment is implemented independently or in conjunction with any other embodiment of the present invention. For example, the method and apparatus disclosed herein may be practiced by using any number of embodiments presented herein. In addition, it should be understood that any embodiment of the present invention can be implemented using one or more of the steps or elements presented in the attached claims.

The word “exemplary” is used herein to mean “used as an example or illustration”. Any embodiment described herein as “exemplary” need not be construed as preferred or having an advantage over other embodiments.

As used herein, the term “neural network” refers to a computational model based on the structure and functions of biological neural networks. Such artificial neural networks are well known in the art and are used to evaluate or approximate functions that may depend on a large number of input data and, in general, are unknown. The main property of neural networks is their ability to self-learn, due to which they can be used in recognition, prediction and control problems or for other purposes. One type of neural network is the cerebellar model of the articular regulator (or, in short, CMAC), which is an associative memory system.

The principle of operation of CMAC is commonly used in control and recognition tasks. In contrast, according to the present invention, CMAC is used to provide bulk data compression. This idea came to the heads of the authors when implementing 3D data reconstruction algorithms, given that the traditional voxel representation is too expensive in memory, and the use of octant trees increases the computational cost and complicates the algorithms themselves (so these algorithms cannot function in real time). The approach proposed in this document is an effective way to compress data (not only two- or three-dimensional data, but also data of higher dimensions) by using small computational costs compared to methods known from the prior art.

FIG. 1 illustrates a data compression apparatus 100 using a neural network approach, in accordance with one example embodiment of the present invention. As shown, the device 100 comprises a memory controller 102, an associative memory 104, an adder 106, a subtractor 108, and a switch 110. The device 100 can operate in two modes, namely, a learning mode and an output mode. It should be noted that each of the controller 102, adder 106, subtractor 108, and switch 110 may be implemented as one or more processors.

In fact, the training mode is the mode of writing the data array to the memory 104, while the output mode is the mode of reading the data array from the memory 104. Such modes are generally accepted when implementing 3D data reconstruction algorithms.

Before the device 100 begins to compress the data, the input data space (for example, which is three-dimensional) is divided into many points or data elements of any suitable shape. Each data element has a coordinate vector X [n] defining its position in the input data space, and a volume vector V [n] defining its volume values in the input data space. In particular, the volume values of data elements are values that characterize the properties of data elements in the input data space. By way of example, these properties of data elements may include color, opacity, or a combination thereof.

In the training mode, when data elements are recorded in the memory 104, the switch 110 is in the on state. In this case, the memory controller 102 calculates suitable memory addresses in the memory 104 using the data element vectors X [n]. In other words, said addressing means that the memory controller 102 associates data elements with corresponding memory cells 104. Each of the memory cells 104 stores a weight value. Further, the memory 104 displays all the weight values that correspond to the cells associated with the data items. An adder 106 sums the weight values to generate the weight vector W [n] and provides the weight vector to the subtractor 108. Subtractor 108 subtracts the weight vector from the vector V [n] to generate the error signal ε [n]. An error signal is used to adjust the required weight values in the memory cells 104.

In particular, the memory controller 102 calculates the addresses of the cells in the memory 104 using the basis vector A [n] obtained using the following formula:

(1)

(one)

, M_i - размерное значение вдоль i-ой оси.where a _k [n] is the kth element of the basis vector A [n] for the n-th moment of time, µ _l is the l-th dimension value of associative memory, N is the dimension of the vector X [n], ρ is the parameter of the neural network, x _j [n] is the jth element of the vector X [n],

, M _i - dimensional value along the i-th axis.

In addition, the error signal adjusts the required weight values of the cells in the memory 104 in accordance with the formula:

(2)

(2)

In the output mode, when data elements are read from the memory 104, the switch 110 is in the off state. In this case, unlike the training mode, there is no error signal transmitted through feedback and regulating the cell weights in the memory 104, and the sum of the weight values, i.e. the vector W [n] is used to calculate the vector of compressed volume values, which is then output.

сжатых объемных значений следующим образом:More specifically, the vector X [n] is input to the memory controller 102, in which the output vector A [n] is calculated using formula (1). Using the vector A [n], the data elements are linked to the memory cells 104. The memory 104 outputs the weight values of the cells to the adder 103. The adder 103 sums all the weight values to form the vector W [n]. After that, adder 103 uses the vector W [n] to form the vector

compressed volume values as follows:

(3)

(3)

FIG. 2 illustrates a three-dimensional representation of memory 104 in FIG. 1 for an example of three-dimensional volumetric data. If the dimensional values for the x, y, z axes are equal to M _x , M _y , M _z respectively, then the total memory capacity is M _x × M _y × M _z . According to the CMAC approach, the corresponding associative memory can be represented as a set of ρ three-dimensional volumes with dimensional values for the x, y, z axes equal to μ _x = M _x / ρ, μ _y = M _y / ρ, μ _z = M _z / ρ, respectively. Moreover, the total amount of associative memory is equal to µ _x × µ _y × µ _z × ρ = (M _x / ρ) × (M _y / ρ) × (M _z / ρ) × ρ. Therefore, for the three-dimensional case, we have a memory gain in the form ρ ² . In the general case, for k-dimensional bulk data and the parameter ρ of the neural network, the memory gain is ρ ^k-1 .

FIG. 3 illustrates a data compression method 300 using a neural network approach, in accordance with one example embodiment of the present invention. The method 300 is performed by the device 100 shown in FIG. 1. The method comprises the following steps:

Step 302: The input data space is divided into data elements, as explained above, i.e. each data element is provided by the vectors X [n] and V [n]. Such separation may be performed by one or more external processors. In some embodiments, these processors may be integrated into device 100.

Step 304: Here, using the coordinate vectors X [n], using the formula (1) determine the addresses of the cells in the associative memory 104 with which data elements should be associated.

Step 306: Associate data items with cells in associative memory 104 based on the determined addresses.

Step 308: All weight values of cells associated with the data elements are summed by adder 106 to obtain the weight vector W [n].

Step 310: The weight vector W [n] is subtracted from the volume vector V [n] to generate an error signal ε [n].

Step 312: Here, it is checked whether the error signal is non-zero. If the error signal is nonzero, the method proceeds to step 314, and to step 316 otherwise.

Step 314: Determine that the error signal is non-zero. Then the error signal is provided to the associative memory 104 for adjusting the weight values of the cells associated with the data elements based on the error signal (in accordance with formula (2)).

Step 316: Determine that the error signal is zero. Then, the vector of compressed volume values is calculated using the adder 106 using the formula (3), and it is derived.

It should be noted that an error signal occurs, i.e. ε [n] is not equal to zero, in case of any changes in the vector X [n]. If the vector X [n] does not change (which corresponds to the unchanged vector V [n]), there is no error signal, and the training mode is not required. Such changes may include a change in the position of the data element, which leads to a new vector X [n] and, therefore, a new vector V [n].

FIG. 4a-e show the results of data compression, for example, for a sinusoidal function in accordance with the method 300 performed in the device 100. In particular, an example of two-dimensional data compression is illustrated for the case of a neural network parameter ρ = 4. In fact, there is a four-layer neural network (k is the layer number). When k changes from 1 to 4, you can see how the compressed data is stored or displayed in each of the layers (Fig. 4a-d). Each of the layers corresponds to a corresponding one or more cells in the memory 104. By summing the compressed data in all the layers, a function close to the original sinusoidal function shown in FIG. 4e can be obtained.

The present invention can be used to store and compress data in various types of computer graphics systems (e.g., reconstructing a 3D model) or machine pattern recognition (e.g., simultaneous localization and display), especially where physical memory is limited due to design requirements (e.g., GPU-based mobile platform or application).

Although exemplary embodiments of the present invention have been disclosed herein, it should be noted that in these embodiments of the present invention, any various changes and modifications may be made without departing from the scope of legal protection that is determined by the appended claims. In the appended claims, the mention of steps or elements in the singular does not exclude the presence of a plurality of such steps or elements, unless explicitly stated otherwise.

Claims (6)

1. A method of compressing data using an approach based on a neural network, the approach based on a neural network consisting of a training mode and an output mode, the method comprising the steps of:
dividing the input data space into a plurality of data elements, each data element having a coordinate vector defining the coordinates of the data element in the input data space and a volume vector defining the volume values of the data element, which are values characterizing the properties of data elements in the input data space;
using coordinate vectors, determine the addresses of cells in associative memory with which data elements should be associated, each cell having a weight value;
associate data elements with cells in associative memory based on specific addresses;
accumulate all weight values of cells associated with data elements to obtain a weight vector;
subtracting the weight vector from the vector of volume values to generate an error signal; and
if the error signal is nonzero, a training mode is activated in which the weight values of the cells associated with the data elements are adjusted based on the error signal; or
if the error signal is zero, an output mode is activated in which a vector of compressed volume values is calculated using a weight vector and then output. 2. The method of claim 1, wherein said determining step comprises the step of:
determine the addresses of cells in associative memory by using the basis vector A [n] obtained using the following formula:

where a _k [n] is the kth element of the basis vector A [n] for the n-th moment of time, µ _l is the l-th dimension value of associative memory, N is the dimension of the coordinate vector X [n], ρ is the parameter of the neural network , x _j [n] is the jth element of the coordinate vector X [n],

, M _i - dimensional value along the i-th axis. 3. The method according to claim 1, in which the weight values of the cells associated with the data elements are adjusted using the following formula:

,
where W [n] is the weight vector for the nth moment of time, X [n] is the coordinate vector for the nth moment of time, V [n] is the vector of volume values for the nth moment of time, A is the basis vector. 4. The method of claim 1, wherein the vector

compressed volume values are calculated using the following formula:

,
where w _i [n-1] is the ith element of the weight vector W [n] for the (n-1) th moment in time. 5. The method of claim 1, wherein the properties of the data elements include color, opacity, or a combination thereof. 6. A data compression device using an approach based on a neural network, the approach based on a neural network consisting of a training mode and an output mode, the device comprising:
associative memory, consisting of cells, and each of the cells has a weight value; and
one or more processors configured to:
dividing the input data space into a plurality of data elements, each data element having a coordinate vector defining the coordinates of the data element in the input data space and a volume vector defining the volume values of the data element, which are values characterizing the properties of data elements in the input data space;
using coordinate vectors, determining the addresses of cells in associative memory with which data elements should be associated;
associating data elements with cells in associative memory based on specific addresses;
accumulation of all weight values of cells associated with data elements to obtain a weight vector;
subtracting the weight vector from the vector of volume values to form an error signal; and
if the error signal is non-zero, enable the training mode, in which the weight values of the cells associated with the data elements are adjusted based on the error signal; or
if the error signal is zero, enable the output mode, in which the vector of compressed volume values is calculated using the weight vector and then output.

Images