# Method for encoding and decoding given three-dimensional objects and device for realization of said method

FIELD: technology for encoding and decoding of given three-dimensional objects, consisting of point texture data, voxel data or octet tree data.

SUBSTANCE: method for encoding data pertaining to three-dimensional objects includes following procedures as follows: forming of three-dimensional objects data, having tree-like structure, with marks assigned to nodes pointing out their types; encoding of data nodes of three-dimensional objects; and forming of three-dimensional objects data for objects, nodes of which are encoded into bit stream.

EFFECT: higher compression level for information about image with depth.

12 cl, 29 dwg

The technical field to which the invention relates.

The present invention relates to a method and apparatus for encoding and decoding data and, in particular, relates to a method and device for encoding and decoding data of three-dimensional objects containing either data point textures or data voxels (volume element of the image), or data ochoterena.

The level of technology

One of the most fundamental goals of research in the field of three-dimensional graphics has always been to create the most realistic graphics on-screen display real images. In this regard, studies of imaging technology using a polygonal model, the result of which was developed many ways of modeling and visualization, which allows to provide a very realistic representation of a three dimensional environment. However, to build complex three-dimensional graphical models require extraordinary efforts and a considerable amount of time. In addition, to represent a complex environment with a high degree of realism is necessary to have a significant amount of data that can lead to very low efficiency of their storage and transmission.

At the present time to represent three-dimensional objects in computer graphics typically use polygon model. If this is the approach of arbitrary shape can be roughly represented by a set of colored polygons, for example, a set of triangles. The last great interest the developments in the field of software algorithms and hardware for graphics, allow the visualization of complex object or scene in a very realistic, a fixed (or mobile) polygon models in real time.

Over the past several years, there has been intensive research on the technology of representing a three-dimensional object mainly because of the difficulties of building polygonal models for a wide variety of real-world objects, the complexity of well-known visualization techniques and limitations in the representation of images as realistic as possible.

To represent three-dimensional objects application program must have a significant number of polygons. For example, the model for a detailed view of the human body should have a few million triangles that too much from the point of view of practical applications. Although recent developments in the field of technology of three-dimensional measurements, such as three-dimensional scanning, provide an opportunity to obtain a complex three-dimensional data, the errors are within acceptable limits, it is still very difficult and expensive to build a polygon model, which is in good agreement with three-dimensional objects. Vdowave is, the visualization algorithm to provide such realistic representations of images, like pictures, too complex to render in real time.

Meanwhile, there is a relatively new way of representation or visualization of an object having a complex geometric structure, namely the representation-based image with depth (DIBR), which was adopted in expanding entertainment infrastructure (AFX) of the MPEG-4 standard. Although the representation of objects in computer graphics typically use polygonal cells (grids), to represent a three-dimensional object in DIBR uses a set of reference images, which cover the visible surface of the three-dimensional object. Each of the reference images is represented by the depth map and the depth map is an array of different distances between the pixels on the image plane and the surface of the three-dimensional object. One of the major benefits of DIBR is something that can be provided with high quality representations of objects simply by using a reference image without the use of polygonal models. In addition, the complexity of the rendering image based on DIBR depends only on the number of pixels forming the DIBR view (i.e., from the resolution of the image DIBR) regardless of scene complexity. DIBR includes the impact SimpleTexture (single texture), PointTexture (dot texture) and Octreelmage (image ochoterena). PointTexture represents an object with pixels PointTexture, visible from a given location of the camera. Each of the pixels PointTexture is represented by a color and a depth (distance between each of the pixels PointTexture and set the camera location and other properties, which help to provide visualization of PointTexture. The set of pixels can be represented along the line of sight. Image PointTexture in General has many, many levels. Figure 1 shows a simple example of one-dimensional image PointTexture. For PointTexture require a substantial amount of data to provide a realistic representation of the objects. In General, the more realistic the image, the higher the density of sampling and more data is required for processing. Therefore, will require effective image compression PointTexture. Figure 2 shows the nodal specifications PointTexture. Figure 2 compression are subjected to field "depth" and "color".

To date, conducted little research on PointTexture, and therefore there are only a few ways based visualization PointTexture. One of the known methods based on PointTexture is a method for compressing multilevel image with depth (LDI), which is revealed in the work of Dual and Li "Compression of the Layered Depth Imae", IEEE Trans. Image Processing, Vol.12, No.3, pp.365-372, March 2003.

In the known designs for compression depth information commonly used algorithms for JPEG-LS. On the other hand, the color information is compressed using the existing coding standards. However, these algorithms JPEG-LS is not supported progressive data compression and progressive transmission of data.

Meanwhile, .S.Kim and S.U.Lee "Compact Encoding of 3D Voxel Surface Based on the Pattern Code Representation, IEEE Trans. Image Processing, Vol.11, N0.8, pp.932-943, 2002, disclosed a method for compressing a surface model of the three-dimensional voxels, using a view-based coded templates (PCR). However, this method does not use a hierarchical structure ochoterena and there is no possibility of implementing schemes progressive compression. In addition, MPEG-4 AFX, developed a method of data compression based on ochoterena [ISO/IEC/JTC1/SC29/WG11 14496-16: 2003, Information Technology-Coding of Audio-Visual Objects-Part 16: Animation Framework extension]. However, this method, like the above-mentioned standard methods may not provide a progressive bit streams.

The invention

In the present invention proposes a method and device for encoding and decoding data of three-dimensional objects containing the data point texture data voxels or data structure ochoterena, and has the ability to compress image information with depth with ensuring the more efficient coding assessment higher coding efficiency data and more efficient lossy compression.

According to one aspect of the present invention proposes a method of encoding data of three-dimensional objects that contain the data point texture data voxels or data structure ochoterena. The method includes forming data of three-dimensional objects having a tree structure in which nodes are supplied with labels that indicate their type; encoding nodes data of three-dimensional objects and generating data of three-dimensional objects whose nodes are encoded in the bit stream.

Preferably, when creating three-dimensional data of the object voxels differed from each other in the data conversion of three-dimensional objects in the data voxels using three-dimensional linking volume and differential assignment of labels to voxels depending on whether they are or not in places where there are objects.

Preferably, when the three-dimensional representation of data objects in a tree structure node with sub-nodes are assigned the label 'S', node whose voxels do not contain objects that were given the label 'W', the node whose all voxels contain objects that were given the label 'In', and the node whose voxels are coded using prediction-based partial coin is placed (PPM), was assigned the label 'P'.

Preferably, the encoding of data nodes of three-dimensional objects include encoding information about the node, which indicates whether or not the current node is a 'S' or Assembly 'R'; encoding the data bits of detailed information (DIB) of the node 'S'if the node information indicates that the current node is an 'S', and the encoding data DIB node 'P', if the node information indicates that the current node is a 'P'.

According to another aspect of the present invention proposes a method of encoding data of three-dimensional objects that contain the data point texture data voxels or data structure ochoterena. The method includes: (a) forming data of three-dimensional objects having a tree structure, the nodes of which is attached labels indicating their types; (b) the consolidation of data nodes of three-dimensional objects by appealing to their labels; (C) encoding the merged nodes; (d) forming data of three-dimensional objects whose combined nodes encoded in the bit stream; and (e) repeat steps (a) through (d) until such time as will not be encoded, the topmost node in the tree structure representing the data of three-dimensional objects.

Preferably, in step (a) node with sub-nodes are assigned the label 'S'; node whose voxel does not contain objects, was assigned the label 'W'; the node, from which all the voxels contain objects that were given the label 'In'; and the node whose voxels are encoded using the algorithm PPM, were assigned the label 'P'.

Preferably, step (b)includes selecting nodes 'S', whose subnodes label 'W' and 'In', and node 'P' nodes as candidates for the Association; selecting among the candidate units as the optimal node for the node, which can minimize the ratio of the difference between ΔD between the number of distorted bits before merging the candidate units and the number of distorted bits after merging the candidate units to the difference ΔR between the number of bits before merging the candidate units and the number of bits after the unification of candidate units; assigning labels to the selected node 'In' and update all the nodes of the candidates, except the node selected as the optimal node.

It is preferable that the difference ΔD was calculated on the basis of the following equation using the Hamming distance between the original model V and its approximationas a measure of distortion:

where X×Y×Z represents the resolution of the original model.

Preferably, step (C) includes encoding the continuous flag that represents the information in asiausa, exist or not in the queue of the node candidates; encoding the position information of the nodes, which indicates the position of each of the candidate units in the queue; encoding information about the node type, which indicates whether or not the current node is a 'S' or Assembly 'R'; and encoding data DIB node 'S'if the information about the nodes indicates that the current node is an 'S', and the encoding data DIB node 'P', if the node information indicates that the current node is a 'P'.

Preferably, the encoding data DIB node 'S' included coding the average value of color information and coding labels eight subnodes of the current node.

Preferably, the encoding data DIB node 'P' included the coding of information about the depth and the encoding of color information.

Preferably, when the encoding information about the depth of all nodes below a given node in the tree structure representing the data of three-dimensional objects was coded on the basis of PPM in accordance with the order of raster scan.

Preferably, when the encoding information about the color values of red (R), green (G) and blue (B) voxels 'In' the current node is encoded by performing differential pulse code modulation (DPCM, DICM) and adaptive arithmetic coding (AAC).

Preferably, the selector specifying the join order, included the selector node candidate, who as candidate units subject to consolidation, selects the nodes 'R' and nodes 'S', whose subnodes label 'W' and 'In'; a selector optimal node from among the nodes in the candidate selects as the optimal node, the node, which can minimize the ratio of the difference between ΔD between the number of distorted bits before merging the candidate units and the number of distorted bits after merging the candidate units to the difference ΔR between the number of bits before merging bits candidate and the number of bits after merging bits candidate, and assigns the label of the selected node 'In'; the block update of candidate units, which updates all the nodes of the candidates, except the node selected as the optimal node.

Preferably, the encoder nodes included encoder continuous flag encoding the continuous flag that represents information indicating whether or not the current node is an end of the compressed bit stream; an encoder position of the nodes, which encodes information about the position of nodes, indicating the position of each of the candidate units in the queue; a selector node 'S or -'R' (SOP), which encodes information about the type of node that indicates whether or not the current node is a 'S' or Assembly 'R'; encoder node 'S', which encodes data DIB node 'S'if the node information indicates that the current node is an 'S'; and an encoder node 'P', which encodes data DIB node 'P', if the node information indicates that the current node is a 'P'.

According to another aspect of the present invention proposes a method of decoding data of three-dimensional objects. The method includes: reading out information on a continuous flag from the bit stream of the encoded data of three-dimensional objects and decoding information about the continuous flag; and decoding the information about the type of nodes in the bit stream; decoding node 'S', if the node type indicates that the current node is an 'S,' and the decoding node PPM, if the information about the type of the site indicates that the current node is a node PPM; and recovery of three-dimensional objects whose nodes are encoded in a tree structure.

According to another aspect of the present invention proposes a method of decoding data of three-dimensional objects. The method includes decoding nodes from a bit stream of coded data of three-dimensional objects and data recovery of three-dimensional objects whose nodes are encoded in a tree structure.

Preferably, the decoding nodes of the bit stream of the encoded data of three-dimensional objects included: read information about the continuous flag from the bit stream of the encoded data of three-dimensional objects and decoding information about the continuous flag; read the position information of nodes indicating which candidate unit in the queue is the current node, and decoding the position information of the node; and decoding the information about the type of nodes in the bit stream; decoding node 'S', if the node type indicates that the current node is an 'S'; and decoding node PPM, if the information about the type of node indicates that the current node is a node PPM.

Preferably, when the decoding node 'S' average color eight subnodes of the current node being decoded data DIB, and eight sub-nodes successively decoded in black is evil (nodes 'In') or white nodes (nodes 'W').

Preferably, when the decoding node PPM current node being decoded on the basis of PPM using the data from the data bits (DIB), and the values R, G and voxels 'In' the current node being decoded by performing reverse coding AAS and reverse modulation DPCM.

According to another aspect of the present invention proposes a device for decoding a bit stream of coded data of three-dimensional objects. The device includes a block read of the bit stream, which receives the bit stream of the encoded data of three-dimensional objects; the decoder nodes, which decodes the bit stream; and a recovery block tree structure, which restores the decoded nodes in the tree structure.

Preferably, the decoder nodes included decoder continuous flag, which decodes the continuous flag indicating whether or not the current node is an end of the bit stream; a decoder of the position information of the nodes, which reads the position information of nodes indicating which node is the candidate queue is the current node, and decodes information about the position of the node; the type selector node that decodes information about the type of nodes in the bit stream; a decoder node S, which decodes the average color eight subnodes of the current node in the form of a data DIB, and then the sequence is correctly decodes eight sub-nodes in the nodes 'In' or hosts 'W'; and the decoder node R, which is based on the PPM encoded data DIB current node, and then decodes the values of R, G and voxels 'In' the current node by performing decoding with inverse AAS and inverse DPCM for the node 'S', if the node type indicates that the current node is a node PPM.

According to another aspect of the present invention offers a medium for recording, read by the computer, which records the program that allows you to perform any of the above methods.

Brief description of drawings

The above and other features and advantages of the present invention will become more apparent from the detailed description of exemplary variants of its implementation with reference to the accompanying drawings, on which:

1 is a diagram illustrating an example of a scatter texture for multi-level image with depth;

2 is a diagram illustrating a sample site for point texture;

figures 3(a) through 3(d) are diagrams illustrating various patterns ochoterena for volumetric data, in which each node is assigned a label;

4 is a curve of distortion from the bit rate obtained when using the data encoding method of three-dimensional objects;

5 is a diagram illustrating the structure of the bit stream of the site;

6 is a diagram illustrating the structure of the flux is and bits of node S;

7 is a diagram illustrating the structure of a bit stream of node P;

figures 8(a) and 8(b) are diagrams illustrating examples of contexts that are used in coding with prediction-based partial match (PPM);

Fig.9 is a diagram illustrating a test model for testing the effectiveness of functioning of the present invention;

figures 10(a) and 10(b) is a table comparing the performance of compression according to the present invention, for the test point model textures, with the performance of other commercial tools (such as WinZip)to do the compression test model PointTexture;

11 is a block diagram of an apparatus for encoding three-dimensional data according to a preferred variant of the present invention;

Fig - detailed block diagram of the selector 11, specifying the join order;

Fig - block diagram of the sequence of operations illustrating operation of selector nodes are candidates for Fig;

Fig - block diagram of the sequence of operations illustrating the operation of the selector specifying the join order;

Fig - detailed block diagram of the encoder nodes 11;

Fig - block diagram of the sequence of operations illustrating operation of the encoder nodes;

Fig - block diagram of the sequence of operations illustrating operation of the encoder nodes S on Fig;

F. g - the block diagram of the sequence of operations illustrating operation of the encoder nodes R Fig;

Fig is a block diagram of a device for decoding data of three-dimensional objects according to a preferred variant of the present invention;

Fig - detailed block diagram of the decoder of nodes Fig;

Fig - block diagram of the sequence of operations illustrating operation of decoder units;

Fig - block diagram of the sequence of operations illustrating the operation of the decoder of nodes S on Fig; and

Fig - block diagram of the sequence of operations illustrating the operation of the decoder of nodes R, Fig.

Detailed description of the invention

Next, with reference to the accompanying drawings should a more detailed description of the method and device for encoding and decoding data of three-dimensional objects containing the data point texture data of the voxels and the data tree structure, according to a preferred variant of the present invention.

Figure 11 shows the block diagram of a device for encoding data of three-dimensional objects according to a preferred variant of the present invention. Refer to 11, where the device includes a generator 1100 tree structure, the selector 1110, specifying the join order, the encoder 1120 units and generator 1130 bit stream.

Generator 1100 tree structure takes on the nnye point textures, data voxels or tree data structures that represent the data of three-dimensional objects, and generates data of three-dimensional objects having a tree structure in which each node is assigned a label to the sites differed from each other. Here, the tree structure is a structure ochoterena.

Further more describes how to create ochoterena. Image PointTexture is converted to volumetric data, and big data in turn are represented by octodurum. Then regional nodes ochoterena subjected to efficient encoding using the encoding method with prediction-based partial matching (PPM). Accordingly, the method of encoding and decoding three-dimensional object according to a preferred variant of the present invention is equivalent to the compression method of the model and PointTexture model ochoterena.

In order to convert the depth information of the three-dimensional object into a volumetric data (data volume), first create a bounding volume. The bounding volume has the same resolution as PointTexture. For example, if we assume that PointTexture represents an image with resolution X×Y and information about the depth of each pixel has a resolution of Z, then create a bounding volume with resolution X×Y×z Start limiting Prampolini is and is located in the lower left front corner of the bounding rectangle. Right voxel has a value of x that is greater than the value of the left waxes; upper voxel has a value that is greater than the value of the lower waxes and rear voxel has a value z, which is greater than the value of the front waxes. The depth information can be immediately converted into binary data volume. All voxels of the data volume initialize by assigning the value of W (white, '0'). After that, the value of the voxels volume data set is equal To (black, '1'), if their location is defined as the pixels of the bitmap texture. Black voxels represent points on a three-dimensional object, and the white voxels are transparent background.

Data volume are ochoterena, and the nodes ochoterena are classified in four different categories. The table below shows the marks, respectively, representing four different categories. If the bounding volume contains the object, the root node is assigned the label 'S', and the bounding volume is divided into eight identical pogoryelov. If the subrange includes only black voxels or white voxels, then the corresponding node is assigned the label 'b' or 'W'. Otherwise, the node corresponding to the subrange, assign the label 'S', and this subrange is additionally divided into eight equal smaller parts. This process vypolnyaetsya, until it reaches the node at the specified depth ochoterena. If the node at the specified depth ochoterena includes both black and white voxels, this node assigns the label 'P', and the values of the voxels included in this site, can be encoded using the PPM method.

Table | |

Label | Comments |

S | Splitting: the site is divided into 8 sub-nodes |

W | White: the node contains only the white voxels |

In | Black paint: node wholly or mainly contains black voxels |

P | PPM: the value of the promissory notes in site is encoded using the algorithm PPM |

In figures 3(a) through 3(d) presents charts illustrating various patterns oktodelete for volumetric data, where each node is assigned a label. In figures 3(a) through 3(d) shows a two-dimensional binary images and their corresponding representations in the form of trees quadrants. In particular, figure 3(a) shows the relationship parent-child relationship in the structure of the quadrants, as in figure 3(b) shows the tree quadrants corresponding to the binary image, where the value of the depth information of the binary image is set to one image can be restored without loss of data by using data encoded using PPM for Quad-tree and three nodes R.

On Fig presents detailed block diagram of the selector 1110 on 11 specifying the join order. The selector 1110, specifying the join order, brings together the nodes for the data of three-dimensional objects represented by a tree structure, by referring to the labels of nodes. As shown in Fig, the selector 1110, specifying the join order, includes a selector 1200 nodes in the candidate selector 1210 optimal node and block 1220 pack of candidate units. The selector 1200 nodes candidate chooses the node labeled 'R', and the node labeled 'S' as candidates for merging. Here the node S whose all child nodes are white nodes (hereinafter designated as the nodes 'W') or black nodes (hereinafter denoted as nodes 'In'), or the nodes 'W' and 'B'can be selected as a candidate for Association.

The selector 1210 optimal node selects as the optimal node the node for which the ratio of the difference between ΔD between the number of distorted bits to the process of merging nodes and the number of distorted bits after the merge process nodes to a difference ΔR between the total number of bits to the process of merging nodes and the total number of bits after the merge process nodes reaches the minimum value. After that, the selector 1210 optimal knot attributed to the selected node labeled 'To'. Block 1220 update nodes candidate updates all the nodes in the candidate, except for the node that is selected as optimal.

Next, with reference to figures 3(a) through 3(d), 13 and 14 a more detailed description of the method of the Association of trees. Figure 3 shows a view oktodelete with labels and merge trees. The nodes of the initial tree repeatedly combined to approximate the original depth information to several levels of detail. Here the merged nodes are the nodes labeled 'R', or nodes whose all child nodes are nodes or nodes In W. for Example, in the tree in figure 3(b) there are four merged node circled in thin circles. Suppose that among the four merged nodes one node that corresponds to the area indicated by the square on a binary image is merged with the node C. the Resulting binary image and the resulting tree is shown in figure 3(C). Now, as shown in figure 3(C), there are three merged node to the left. Then one of the three merged nodes (e.g., node P, on the far left side of the tree shown in figure 3(C)) are combined in the node C. Then combine becomes a node, which corresponds to the left upper quadrant of the approximated model in figure 3(d) and whose all child nodes are nodes 'In' or hosts 'W'. This process of Association n of the tree is performed continuously, until all nodes of the tree will not be United together under one root node.

On Fig presents a flowchart illustrating the operation of the selector 1200 candidate units. Assume that 'i' represents the sequence number of each node, and 'count' (count) represents the number of candidate units; and at step 1300 'i' and 'count' initialize by assigning a value of 0. If at step 1310, the node is assigned the label 'S' or 'P', then this node is selected as a node of the candidate, and then it is stored in the queue, and the variable 'count' at step 1330 is incremented by 1. Here as nodes candidate among nodes 'S' can be selected only those nodes that have all the descendant nodes are nodes 'W' or hosts 'In'or hosts 'W' and 'In'. If the node is not a node 'S'or node 'P', then at step 1310 to the next node at step 1320. Steps 1310 through 1330 is performed repeatedly until 'i' indicates the last node (step 1340).

Sites that require merging with each other, are selected from a set of merged nodes, and minimize the ratio of ΔD to ΔR at a given speed, as shown in the following equation (1).

In equation (1) ΔR represents the difference between the total number (R_{a}) bits before the process of merging nodes and the total number (R_{b}) bits after the merge process nodes, and Δ
D represents the difference between the number of (D_{a}) distorted beats to the process of merging nodes and the number (D_{b}) distorted bits after the merge process nodes. When nodes are merged, the required bit rate is reduced, but the degree of distortion of the approximated model increases. Therefore, it is necessary to find the nodes that can minimize the likelihood of distortion of the approximated model and can provide a maximum reduction of the required transmission speed in bits, as only nodes will be merged with each other.

In order to calculate ΔD as a measure of distortion, use the Hamming distance between the original model V and the corresponding approximation.

X×Y×Z represents the resolution of the model.

To calculate ΔD, you must calculate the number of bits required (i.e., the desired transmission rate in bits) to represent ochoterena and its nodes PPM. However, this required bit rate to calculate very difficult. Therefore, the required bit rate is calculated by using bits of the model tree and bits PPM in several test models.

On Fig shows the block diagram of the algorithm, illustrating the operation of the selector 1210, specifying the join order. Contact Fig, the de at step 1410 of the number of nodes, which is selected by the selector 1200 candidate units as nodes in the candidate chosen as the optimal site for which can be obtained the minimum value of equation (1). At step 1420 the selected optimal node assigns the label 'In'. At step 1430, the node labeled 'In' is removed from the queue. At step 1440, the queue is updated. Steps from 1410 to 1440 repeated many times until all nodes are not merged with each other (step 1450).

The encoder 1120 nodes encodes the merged node. On Fig presents detailed block diagram of the encoder 1120 nodes. Contact Fig, where the encoder 1120 nodes includes an encoder 1500 continuous flag encoder 1510 position of the nodes, the selector 1520 knots S-or-P (SOP), the encoder 1530 nodes S and encoder 1540 nodes R.

The encoder 1500 continuous flag encodes the continuous flag that indicates whether or not the current node is an end of the compressed bit stream. If the current node is not the end of the compressed bit stream, then the continuous flag is assigned the value "true". Otherwise, the continuous flag is assigned a value of "false". Encoder 1510 provisions of nodes, which includes all of the candidate units, where the nodes selected by the selector 1200 nodes candidate as the candidate units, encodes information about the position of nodes, which indicates the position of each of the candidate units in the queue of nodes here the candidates. The selector 1520 knots (SOP) encodes information about the type of nodes that indicates whether the current node is a node S or node R. the Encoder 1530 nodes S encodes the data bits of detailed information (DIB) of node P, if the node type indicates that the current node is R.

On Fig presents a flowchart of the sequence of operations illustrating operation of the encoder 1120 nodes. Contact Fig, where at step 1600 is encoded continuous flag. As described above, the continuous flag indicates whether or not the current node is an end of the compressed bit stream. If the current node is not the end of the compressed bit stream, then the continuous flag is assigned the value "true". Otherwise, the continuous flag is assigned a value of "false". At step 1600 is encoded position information of the node. At step 1620 check whether or not the merged node by node R. If the merged node is P, then at step 1630 encode node R. otherwise, perform the encoding node S. the Stages from 1600 to 1640 perform repeatedly until then, until you have coded all the nodes (step 1650).

On Fig presents a flowchart of the sequence of operations illustrating operation of the encoder 1520 knots S. Contact Fig; at step 1700 is encoded information about the average color. At step 1710 encode labels eight sub-nodes.

the and Fig presents a flowchart of the sequence of operations, illustrating operation of the encoder 1530 nodes R. Refer to Fig; phase 1800 encoded information about the depth using PPM. At step 1810 is encoded color information using differential pulse code modulation (DPCM).

In particular, the units are combined in a predetermined order in accordance with their priorities determined using equation (1), while streams of bits to encode in the reverse order. In other words, the node that merged later to encode the encoded node, United earlier. Therefore, the decoder can reconstruct the three-dimensional model, starting with the coarse model and ending with the most detailed model of the compressed bit stream by parsing the compressed bit stream. 4 shows the curve of dependence of the distortion of transmission rate in bits obtained by using the above-mentioned way of grouping nodes.

Next, a more detailed description of the structure of the bit stream. The compressed bit stream contains data about the nodes ochoterena. The order of the nodes in the compressed bit stream is reversed from the order of the join nodes as described above. Figure 5 shows a diagram illustrating the structure of a compressed bit stream of the specified node. Refer to figure 5; information about the site contains continuous flag, position data, the data published SOP DIB.

Continuous flag indicates whether or not the specified node is an end of the compressed bit stream. All data constituting information about the node in figure 5, are subjected to statistical coding using adaptive arithmetic coder (AAC). Position data indicate required or no splitting or coding based on a PPM node 'In'. For example, suppose that the decoder restores the approximated model, shown in figure 3(d)using all the data. Oktodelete in figure 3(d) includes four nodes 'In', which are the nodes are candidates for merging. To get more detailed model, shown in figure 3(C), the encoder informs the decoder about the fact that among the four nodes 'In' the second node to the left in oktodelete must be encoded using the algorithm PPM. If there is more than one node is a candidate for merging, as shown in figure 3(d), the position data is encoded data, in what order should I encode using PPM, each of the candidate units, i.e. nodes 'In'. If there is only one candidate unit (node 'B'), the position data is not necessary, and therefore the encoding position data is not required. Data SOP indicate whether to split into eight descendant nodes or to encode using Rsarea the specified node. If the data SOP indicate that predefined node is an 'S', data DIB contains eight flags indicating which the average color of the given node, and indicating, or are no child nodes a given node nodes 'W'. Nodes, not nodes 'W', temporarily considered as nodes and therefore are stored in the queue, where the recorded hosts candidates 'In' for the next bit stream. Figure 6 shows the structure of a node 'S'.

If the data SOP indicate that the specified node is a 'P', the information about the intensity of the voxels 'in' In a given node is subjected to encoding using PPM, and using DPCM encoded color information of the voxels 'In'. 7 shows the structure of the bit stream node 'P'. Method PPM was first proposed Clery (Cleary) and Wittens (Witten) for data compression Fax transmission without loss of data.

Next, a more detailed description of the coding PPM. As described above, information about the depth represented by binary values of the voxels. The voxels 'W' represent a transparent background, and the voxels '' represent a three-dimensional object. Binary voxels in the node 'P' subjected to encoding based on the PPM through the use of voxels adjacent to a binary voxels as contexts. On Fig(a) and 8(b) shows examples of contexts. Thirteen all voxels are used as contexts for coded what I rectangular waxes.
In accordance with a raster scan voxels 'W' set to '0'and the voxels 'In' set to '1'. These thirteen bits, that is, thirteen round voxels, are used as contexts for rectangular waxes shown in Fig(b). In this case, the contexts for rectangular waxes can be represented as '0011101000011'that corresponds to the number of contexts is equal to 2^{13}. However, 2^{13}contexts too much for calculations. Accordingly, there is a need to reduce the number of contexts. Through simulation selected voxels, which slightly increase the entropy, even if you delete them. First remove the two waxes. Then remove another voxel. These three waxes marked on Fig(a) the sign 'X'. Adaptive arithmetic coder compresses the voxels, using the given context.

Black square on Fig(b) is encoded, and the black circles on Fig(a) and 8(b) are used as contexts. On Fig(a) voxels marked by the symbol 'X', are removed by the voxels.

After encoding the information about the depth coding using DPCM color values R, G and waxes 'in' In a given node according to the order defined by the raster scan. In particular, the color values R, G and waxes 'In' evaluate on the basis of the color values R, G, is In the previous waxes 'In'. Residual evaluation encode using an arithmetic coder.

Generator 1130 flow creates data bits encoded on the nodes, in the form of a bit stream.

In the present invention, the data of three-dimensional objects encode using the method of progressive coding. However, a three-dimensional object may be encoded using the method of lossless encoding or the encoding is lossy. When you encode the entire stream of bits as a whole as a way of encoding can be used for lossless encoding. On the other hand, when encode only part of the bit stream, starting with the root node of the tree structure corresponding to this stream of bits to a given node at a lower level tree structure, as a method of encoding you can select the encoding is lossy.

Next, a more detailed description of the method and apparatus for decoding data of three-dimensional objects.

On Fig shows the block diagram of a device for decoding data of three-dimensional objects according to a preferred variant of the present invention. Contact Fig: the device includes a block read 1900 reading of the bit stream, the decoder 1910 nodes and block 1920 recovery tree structure. The 1900 block of the read bit stream receives the encoded bit stream three-dimensional data about the projects, the decoder 1910 node decodes the encoded bit stream, and the block 1920 recovery tree structure restores the decoded nodes in a tree structure.

On Fig presents detailed block diagram of the decoder 1910 nodes. The decoder 1910 nodes includes a decoder 2000 continuous flag decoder 2010 information about the position of nodes, selector 2020 type of nodes, the decoder 2030 nodes S and decoder 2040 nodes R.

The decoder 2000 continuous flag reads the information about the continuous flag from the encoded stream of data bits of three-dimensional objects and decodes the encoded bit stream. Decoder 2010 information about the position of nodes reads the position information of the nodes from the encoded bit stream and decodes the read position information of the nodes forming position information, which indicates where the queue is the current node. The selector 2020 type node decodes information about the type of node. If the node type indicates that the current node is S, then the decoder 2030 nodes S decodes the average color of the eight sub-nodes in the form of a data DIB, and then sequentially decodes the eight sub-nodes in the nodes 'b' or 'W'. If the node type indicates that the current node is PPM, the decoder 2040 nodes R decodes, using the PPM data DIB current node. The decoder 2040 nodes R decodes the colors R, G and voxels 'In' the current node, performing a reverse coding AAS and reverse modulation DPCM.

On Fig presents a flowchart of the sequence of operations illustrating the operation of the decoder 1910 nodes. Contact Fig: 2100 decode continuous flag. At step 2110 decode data on the situation. At step 2120 check whether or not the current node is a 'P'. If the current node is a 'P', then the current node at step 2130 decode, using the method of decoding nodes 'R'. Otherwise, the current node decode, using the method of decoding 'S'. Steps by 2100 2130 perform repeatedly up until all nodes are decoded (step 2150).

On Fig presents a flowchart of the sequence of operations illustrating the operation of the decoder 2020 nodes S. Contact Fig: 2200 decode information about the average color. At step 2210 decode labels eight subnodes of the current node.

On Fig presents a flowchart of the sequence of operations illustrating the operation of the decoder 2030 nodes R. Refer to Fig: 2300 decode the depth information PPM. At step 2310 decode the color information by performing an inverse DPCM. In particular, decode based on PPM current node, using data from the DIB, and the values R, G, and black voxels of the current node decode by performing reverse AAS and inverse DPCM.

Further more describes a method of decoding data of three-dimensional objects according to the present invention.

The method of decoding data of three-dimensional objects according to the present invention is similar to the data encoding method of three-dimensional objects according to the present invention. The decoder reads the continuous flag bit stream and checks whether or not the current node is an end of the bit stream. Then, the decoder reads the position data and the data of the SOP and determines which nodes should be split or decode using PPM, based on the read position data and data SOP. If the current node is an 'S', the color values of all voxels of the current node is temporarily set equal to the average values of the color values R, G and b data DIB. The color values of the voxels of the current node update when receiving data about the nodes descendants of the current node. If the current node is a 'P', then information about the depth and color of the voxels 'In' the current node is restored without loss using data DIB.

In the present invention, the decoding data of three-dimensional objects is "progressive" way. When "progressive" way nodes decode in a predetermined order in which the decoded bit streams of image data. Therefore, if the image data are displayed on the screen, then the decoded nodes are displayed on the screen sequentially in the order from the upper node to the lower node. With therefore, its, when the decoding process reaches the lower nodes in the tree structure representing the data of three-dimensional objects, the image displayed on the screen becomes more detailed and clear. When the decoding process ends after decoding the last node, the screen displays the most detailed and clear image.

As described above, in the present invention, the data of three-dimensional objects decode "progressive" way. However, a three-dimensional object can be decoded using the method of decoding a lossless or a method of decoding lossy. When decode the entire stream of bits as a whole, as a way of decoding it is possible to choose the decoding lossless. On the other hand, if the decoded only part of the bit stream, starting with the root node of the tree structure corresponding to the bit stream to the specified node at a lower level tree structure, as a way of decoding it is possible to choose the decoding lossy.

The effectiveness of methods of data encoding and decoding three-dimensional objects according to the present invention was assessed using the test model shown in Fig. 9(a) through 9(h). The test model shown in Fig. 9(a) through 9(e) have a resolution of 256×256×256, and the test model shown n the Fig. 9(f) 9(h), have a resolution of 512×512×512.

Figure 10(a) and 10(b) presents a table illustrating the efficiency of data compression in the present invention compared to WinZip. When using the present invention requires only 22˜59% of the size of the file that will need WinZip for processing depth information. For processing color information in the present invention requires only 59˜81% of the file size, which is required for WinZip. However, from the point of view of processing the "flat" model, WinZip shows higher efficiency than the present invention because the "flat" model contains only a few colors, and WinZip, which is an encoder-based dictionary, like better to work with "flat" model. In the present invention for compression depth information and color information is required only 49˜75% of the file size required for WinZip.

It is noteworthy that the present invention supports progressive data transfer and progressive decoding data that is not available to the encoder WinZip. Progressive data transfer and progressive decoding of the data is preferred because it facilitates the adaptation of the flow of bits to an environment with limited bandwidth and viewing of three-dimensional models.

In the present invention serves sposobnostyah data compression for PointTexture. When using the method of progressive compression of the data pixels are closely related to each other in the sense vectors color and depth information. In the present invention, the depth information and the color information can be efficiently encoded using the PPM method in the structure ochoterena. Numerous simulation results show that the present invention provides a higher compression ratio than the universal coder LempelZiv, i.e. WinZip.

The present invention can be implemented in the form of programs that are read by a computer, recorded on the recording medium, is read by the computer. The recording media readable by a computer, includes all types of recording devices that can record data can be read by the computer. For example, the medium for recording is read by the computer includes a read-only memory (ROM), RAM, ROM, CD-ROM (CD-ROM), magnetic tape, floppy disk, optical storage device, and the carrier signal, for example signal providing data transmission over the Internet. The medium for recording is read by the computer, can be distributed over multiple computer systems that are connected to each other in the form of a network; in this case, the data can be stored in the medium for recording is read by the computer, decentralized.

Although infusion is her invention was shown and described in detail with reference to exemplary embodiments of its implementation, specialists in the art it is obvious that it can be made various changes in form and detail within the essence and scope of the present invention defined by the following claims.

1. The data encoding method of three-dimensional objects that contain the data point texture data voxels or data structure ochoterena, and the method comprises the steps: forming data of three-dimensional objects having a tree structure, the nodes of which is attached labels indicating their types; coding of data nodes of three-dimensional objects, which perform encoding information about the node, which indicates whether or not the current node is a 'S' or node, 'P', and encoding the data bits of detailed information (DIB) of the node 'S'if the node information indicates that the current the node is an 'S', and the encoding data DIB node 'P', if the node information indicates that the current node is a 'P', and the step of forming the data of three-dimensional objects whose nodes are encoded in the bit stream.

2. The method according to claim 1, in which when forming the three-dimensional data of the object voxels differ from each other in the data conversion of three-dimensional objects in the data voxels using three-dimensional linking volume and the differential provian what I label the voxels in the matter or not they were in places where there are objects.

3. The method according to claim 2, in which the three-dimensional representation of data objects in a tree structure node with sub-nodes, assign the label 'S', node whose voxels do not contain objects, assign the label 'W', the node whose all voxels contain objects, assign the label 'B', and the node whose voxels are coded using prediction-based partial matching (PPM), assign the label 'P'.

4. The method according to claim 1, in which when encoding nodes data of three-dimensional objects encode only some of the nodes in the three-dimensional data of objects within the root node to a given downstream node.

5. The method according to claim 1, in which when encoding nodes data of three-dimensional objects encode all data nodes of three-dimensional objects.

6. The data encoding method of three-dimensional objects that contain the data point texture data voxels or data structure ochoterena, and the method comprises the steps of: (a) forming data of three-dimensional objects having a tree structure, the nodes of which is attached labels indicating their types; (b) the consolidation of data nodes of three-dimensional objects by appealing to their labels; (c) encoding the merged nodes, containing the coding continuous flag, which represents the information is, indicates that there are or not in the queue of the node candidates; encoding the position information of the nodes, which indicates the position of each of the candidate units in the queue; encoding type information of the nodes, which indicates whether or not the current node is a 'S' or node 'P'; data coding DIB node 'S'if the information about the nodes indicates that the current node is an 'S', and the encoding data DIB node 'P', if the information about the nodes indicates that the current node is a 'P'; (d) forming data of three-dimensional objects whose combined nodes encode the bit stream; (e) repeat steps (a) through (d) until such time as will not be encoded, the topmost node in the tree structure representing the data of three-dimensional objects.

7. The method according to claim 6, in which step (a) node with sub-nodes, assign the label 'S'; node whose voxels do not contain objects, assign the label 'W'; the node, from which all the voxels contain objects, assign the label 'B', and the node whose voxels are coded using the PPM algorithm, assign the label 'P'.

8. The method according to claim 7, in which step (b) contains a selection of nodes 'P' and nodes 'S', whose subnodes label 'W' and 'B'nodes as candidates for the Association; selecting among the candidate units as the optimal node for the node, which can minimize the ratio of the difference between 9 D between the number of distorted bits before merging the candidate units and the number of distorted bits after merging the candidate units to the difference ΔR between the number of bits before merging the candidate units and the number of bits after merging the candidate units; assigning labels to the selected node 'B'; update all the nodes of the candidates except the node selected as the optimal node.

9. The method according to claim 8, in which ΔD calculates, on the basis of the following equation using the Hamming distance between the original model V and its approximationas a measure of distortion:

where X×Y×Z represents the resolution of the original model.

10. The method according to claim 6, in which the data coding DIB node 'S' contains the encoding of the average value of color information and coding labels eight subnodes of the current node.

11. The method according to claim 6, in which the data coding DIB node 'P' contains the coding information about the depth and the encoding of color information.

12. The way po, which was used for encoding information about the depth of all nodes below a given node in the tree structure representing the data of three-dimensional objects, encode based on PPM in accordance with the order of raster scanning is used by the I specified number of contexts.

13. The method according to claim 11, which was used for encoding information about the color values of red (R), green (G) and blue (B) voxels 'B' of the current node code by performing differential pulse code modulation (DPCM) and adaptive arithmetic coding (AAC).

14. The method according to claim 6, in which step (C) encode only some of the joint nodes that are within from the first node to the node with the given ID.

15. The method according to claim 6, in which step (C) encode all merged nodes.

16. Device for encoding data of three-dimensional objects that contain the data point texture data voxels or data structure ochoterena, and the device comprises: generating a tree structure, which generates data of three-dimensional objects having a tree structure, the nodes of which is attached labels indicating their types; a selector that specifies the order of the Association, which brings together the nodes of the data of three-dimensional objects by appealing to their labels; the encoder nodes, which encodes the merged nodes, and which contains: encoder continuous flag encoding the continuous flag that represents information indicating whether or not the current node is an end of the compressed the bit stream; an encoder position of the nodes, which encodes information about the position of nodes, indicating the position of each of the C of candidate units in the queue; the selector node 'S' or 'P' (SOP), which encodes information about the type of node that indicates whether or not the current node is a 'S' or node 'P'; encoder node S, which encodes data DIB node 'S'if the node information indicates that the current node is an 'S'; and an encoder node P, which encodes data DIB node 'P', if the node information indicates that the current node is a 'P'; and a bit stream generator that produces the data of three-dimensional objects whose combined nodes encoded in the bit stream.

17. The device according to clause 16, in which the selector specifying the join order, contains the selector of the node candidates as candidate units subject to consolidation, selects the nodes 'P' and nodes 'S', whose subnodes label 'W' and 'B'; a selector optimal node from among the nodes in the candidate selects as the optimal node, the node, which can minimize the ratio of the difference between ΔD between the number of distorted bits before merging the candidate units and the number of distorted bits after merging the candidate units to the difference ΔR between the number of bits before merging the candidate units and the number of bits after merging the candidate units, and assigns the label of the selected node 'B'; block update of candidate units, which updates all the nodes of the candidates, except the node selected is the quality of the optimal node.

18. The device according to clause 16, in which the encoder nodes encodes only some of the joint nodes that are within from the first node to the node with the given ID.

19. The device according to clause 16, in which the encoder nodes encodes all merged nodes.

20. The method of decoding data of three-dimensional objects, containing the steps of reading information about the continuous flag from the bit stream of the encoded data of three-dimensional objects and decoding information about the continuous flag; decoding information about the type of node in the bit stream; decoding node 'S', if the node type indicates that the current node is an 'S', and decoding node PPM, if the node type indicates that the current node is a node PPM; data recovery of three-dimensional objects whose nodes are encoded in a tree structure.

21. The method of decoding data of three-dimensional objects containing the decoding nodes from a bit stream of coded data of three-dimensional objects, which includes the steps of reading information about the continuous flag from the bit stream of the encoded data of three-dimensional objects and decoding information about the continuous flag; read the position information of nodes indicating which candidate unit in the queue is the current node, and decoding the position information of nodes; decoding information about the IPE node in the bit stream; decoding node 'S', if the node type indicates that the current node is an 'S'; decoding node PPM, if the node type indicates that the current node is a node PPM; data recovery of three-dimensional objects whose nodes are encoded in a tree structure.

22. The method according to item 21, which when decoding node 'S' average color eight subnodes of the current node decode data DIB, and eight sub-nodes sequentially decode in black nodes (nodes 'B') or white nodes (nodes 'W').

23. The method according to item 22, which when decoding node PPM current node decode-based PPM using the data from the data bits (DIB), and the values R, G and B voxels 'B' of the current node decode by performing reverse coding AAS and reverse modulation DPCM.

24. A device for decoding a bit stream of coded data of three-dimensional objects, and the device comprises a block read of the bit stream, which receives the bit stream of the encoded data of three-dimensional objects; the decoder nodes, which decodes the bit stream and which contains a decoder continuous flag, which decodes the continuous flag indicating whether or not the current node is an end of the bit stream; a decoder of the position information of the nodes, which reads the position information of nodes indicating which candidate unit, n is held in the queue, is the current node, and decodes information about the position of nodes; a selector node type that decodes information about the type of node in the bit stream; a selector node type that decodes information about the node type of the bit stream; a decoder node S, which decodes the average color eight subnodes of the current node in the form of a data DIB, and then sequentially decodes the eight sub-nodes in the nodes 'B' or hosts 'W'; decoder node P, which is based on the PPM encoded data DIB current node, and then decodes the values of R,G and B voxels 'B' the current node by performing decoding with inverse AAS and inverse DPCM for the node 'S', if the node type indicates that the current node is a node PPM; recovery block tree structure, which restores the decoded nodes in the tree structure.

25. The recording media readable by the computer on which you write a program that allows you to perform the method according to any one of claims 1 to 5.

26. The recording media readable by the computer on which you write a program that allows you to perform the method according to any of p-15.

27. The recording media readable by the computer on which you write a program that allows you to perform the method according to claim 20.

28. The recording media readable by the computer on which you write a program that allows you to perform the method according to any of PP-23.

29. Nositelstve, read by the computer, for use in a device for encoding data of three-dimensional objects according to any one of PP-19.

30. The recording media readable by a computer, for use in a device for decoding a bit stream of coded data of three-dimensional objects by point 24.

**Same patents:**

FIELD: computer science.

SUBSTANCE: method includes forming a computer model of object, determining mass-center and inertial characteristics of object model, while according to first variant, model of object is made in form of mass-inertia imitator, being an imitator of mass and main center momentums of inertia, according to second variant, model of object is made in form of assembly imitator, in form of assembly, received by combining dimensional imitator of object model, in form of three-dimensional model with appropriate outer geometry, and mass imitator and main central inertia momentums, and according to third variant object model is formed as component imitator, in form of assembly, consisting of dimensional object model imitator, in form of three-dimensional model of object with appropriate outer geometry.

EFFECT: higher efficiency, broader functional capabilities, lower laboriousness.

3 cl, 5 dwg

FIELD: computer-laser breadboarding.

SUBSTANCE: using a system for three-dimensional geometric modeling, volumetric model of product is made, separated on thin transverse layers and hard model is synthesized layer-wise, thickness A of transverse layers is picked from condition, where A≤F, where F is an allowed value for nominal profile of model surface and generatrix of model surface profile passes through middle line of transverse layers.

EFFECT: shorter time needed for manufacture of solid model.

1 dwg

FIELD: computer-laser breadboarding.

SUBSTANCE: using a system for three-dimensional geometric modeling, volumetric model of product is made, separated on thin transverse layers and hard model is synthesized layer-wise, thickness A of transverse layers is picked from condition, where A≤F, where F is an allowed value for nominal profile of model surface and generatrix of model surface profile passes through middle line of transverse layers.

EFFECT: shorter time needed for manufacture of solid model.

1 dwg

FIELD: technology for encoding and decoding of given three-dimensional objects, consisting of point texture data, voxel data or octet tree data.

SUBSTANCE: method for encoding data pertaining to three-dimensional objects includes following procedures as follows: forming of three-dimensional objects data, having tree-like structure, with marks assigned to nodes pointing out their types; encoding of data nodes of three-dimensional objects; and forming of three-dimensional objects data for objects, nodes of which are encoded into bit stream.

EFFECT: higher compression level for information about image with depth.

12 cl, 29 dwg

FIELD: information technology.

SUBSTANCE: disclosed is a method for graphic processing, comprising steps on which: depth of at least two blocks of pixels is tested in parallel, and it is determined whether all pixels of both blocks are excluded and if so, these blocks are ignored when testing depth. In another version, said block of pixels is a rectangular array of pixels, and pixels with minimum and maximum depth values among all pixels in the block correspond to corners of the said rectangular array of pixels.

EFFECT: high rate of testing depth in order to exclude a hidden surface during graphic processing.

10 cl, 4 dwg

FIELD: information technology.

SUBSTANCE: invention relates to image processing, in particular, to a method of objects replacement in a video stream. Said technical result is achieved due to that a stereoscopic field image is created, which serves to measure a distance from the camera and to determine foreground objects, background objects and overlapping objects. Stereoscopic image can be provided by a 3D camera or it can be created by means of a signal coming from one or several cameras. Texture of objects to be replaced can be static or dynamic. Method requires no special equipment to monitor the camera position, and it can be used for live content, as well as an archive material. Invention uses the advantage of initial material to be replaced, in a specific case, when the object to be replaced is filled in electronically.

EFFECT: technical result is inserting replacement images into a video stream without the need to receive and transmit parameters of the camera via a sensor equipment mounted on a tripod and without the need of a static model of the real environment.

21 cl, 8 dwg

FIELD: computer-laser breadboarding.

SUBSTANCE: using a system for three-dimensional geometric modeling, volumetric model of product is made, separated on thin transverse layers and hard model is synthesized layer-wise, thickness A of transverse layers is picked from condition, where A≤F, where F is an allowed value for nominal profile of model surface and generatrix of model surface profile passes through middle line of transverse layers.

EFFECT: shorter time needed for manufacture of solid model.

1 dwg

FIELD: computer-laser breadboarding.

EFFECT: shorter time needed for manufacture of solid model.

1 dwg

FIELD: computer science.

SUBSTANCE: method includes forming a computer model of object, determining mass-center and inertial characteristics of object model, while according to first variant, model of object is made in form of mass-inertia imitator, being an imitator of mass and main center momentums of inertia, according to second variant, model of object is made in form of assembly imitator, in form of assembly, received by combining dimensional imitator of object model, in form of three-dimensional model with appropriate outer geometry, and mass imitator and main central inertia momentums, and according to third variant object model is formed as component imitator, in form of assembly, consisting of dimensional object model imitator, in form of three-dimensional model of object with appropriate outer geometry.

EFFECT: higher efficiency, broader functional capabilities, lower laboriousness.

3 cl, 5 dwg