ES2374064T3

Apparatus and method for depth image-based representation of 3-dimensional object

Abstract

A node structure to represent a three-dimensional object, the node structure comprising: a field of octa-tree resolution, in which the maximum value of the terminal leaves of the tree is recorded along the side of a surrounding cube containing an object; an octárbol field in which a structure of the internal node of the octárbol is registered; a camera index field in which the voxel indices of the octree of a reference image corresponding to the internal node are recorded; and an image field in which the reference image is registered.

ES2374064T3, drawing sheet 1 — Sheet 1 of 34

Term

Term ended

Projected expiry passed 27 November 2022, 3.8 years ago.

7 claims: 1 independent, 6 dependent

1
ES 2 374 064 T3 REIVINDICACIONES 1. Una estructura de nodos para representar un objeto tridimensional, comprendiendo la estructura de nodos:un campo de resoluciónoctárbol, en el cual se registra el máximo valor de las hojas terminales del octárbol a lo largo del lado de un cubo circundante que contiene un objeto;un campo de octárbol en el cual se registra una estructura del nodo interno del octárbol;un campo de índice de cámara en el cual se registran los índices de voxels del octárbol de una imagen de referencia correspondiente al nodo interno;y un campo de imagen en el cual se registra la imagen de referencia.
2
La estructura de nodos según la reivindicación 1, en la cual el nodo interno está representado por un octeto, y la información de nodos registrada en los flujos de bits que constituyen el octeto representa la presencia o ausencia de nodos hijos de nodos hijos pertenecientes al nodo interno.
3
La estructura de nodos según la reivindicación 1, en la cual la imagen de referencia es una imagen con profundidad que incluye información de punto de vista y una imagen en color correspondiente a la información de punto de vista.
4
La estructura de nodos según la reivindicación 3, en el cual la información de punto de vista comprende:un campo de punto de vista en el cual se registran los puntos de vista desde los cuales se visualiza un plano de imagen;un campo de campoDeVisión en el cual se registra un área de visibilidad desde el punto de vista hasta el plano de imagen;y un campo ortográfico en el cual se registra un procedimiento de proyección desde el punto de vista hasta el plano de imagen.
5
La estructura de nodos según la reivindicación 4, en la cual el campo de punto de vista comprende:un campo de posición donde se registra la posición de un punto de vista;y un campo de orientación donde se registra la orientación del punto de vista, siendo la posición una ubicación relativa al origen del sistema de coordenadas, y siendo la orientación una magnitud de rotación con respecto a la orientación por omisión.
6
La estructura de nodos según la reivindicación 4, en la cual el procedimiento de proyección es un procedimiento de proyección ortogonal, y el ancho y la altura del área de visibilidad corresponden, respectivamente, al ancho y a la altura de un plano de imagen.
7
La estructura de nodos según la reivindicación 3, en la cual la imagen en color es una TexturaSimple que consiste en una imagen plana que contiene el color para cada píxel.

Independent claims7

854 paragraphs in 35 sections, as filed

ES 2 374 064 T3

DESCRIPTION

Node structure to represent three-dimensional objects using images with depth

The present invention relates to a node structure for representing three-dimensional (3D) objects based on images with depth and, more specifically, to a node structure for representing objects using images with depth information.

Since the beginning of research on three-dimensional (3D) graphics, the ultimate goal of researchers is to synthesize a realistic graphic scene, like a real image. Therefore, research has been carried out on traditional technologies of representation, using polygonal models, and as a result, technologies of modeling and representation have developed enough to provide very realistic three-dimensional environments. However, the process to generate a complicated model requires a great deal of effort by experts, and is time consuming. Furthermore, a realistic and complicated environment requires a huge amount of information and causes efficiency in storage and transmission to be reduced.

Currently, polygon models are commonly used for the representation of three-dimensional objects in computer graphics. An arbitrary shape can be represented essentially by sets of colored polygons, that is, triangles. Highly advanced software algorithms and graphics hardware development make it possible to display complex objects and scenes as highly realistic moving and still image polygonal models.

However, the search for alternative three-dimensional representations has been very active during the last decade. The main reasons for this include the difficulty of building polygonal models for real-world objects, as well as the complexity of rendering and unsatisfactory quality to produce a truly realistic photographic scene.

Demanding applications require huge amounts of polygons; for example, the detailed model of a human body contains several million triangles, which are not easy to manipulate. Although recent progress in distance finding techniques such as laser distance scanning allows us to acquire dense distance data with tolerable error, it is still very expensive and also very difficult to obtain a seamless full polygonal model of the entire object. . On the other hand, rendering algorithms for realistic photographic quality are computationally complex and therefore far from real-time rendering.

It is an aspect of this invention to provide a node structure for representing three-dimensional (3D) objects using depth images, for computer graphics and animation, called depth image-based rendering (DIBR), which has been adopted in the Environment Extension. Animation (AFX) of the MPEG-4 standard.

According to one aspect of the invention, a node structure according to claim 1 is a depth field in which a depth value is recorded for each pixel.

According to the present invention, the rendering time for image-based nodes is proportional to the number of pixels in the reference and output images but, in general, not to the geometric complexity, as in the polygonal case. Additionally, when image-based rendering is applied to real-world objects and scenes, the photo-realistic rendering of a natural scene is made possible without the use of millions of polygons and expensive calculations.

The foregoing objects and advantages of the present invention will become more apparent as the preferred embodiments thereof are described in detail with reference to the accompanying drawings, in which:

FIG. 1 is a diagram of IBR examples embedded in current reference software;

FIG. 2 is a diagram of an octree structure and the order of the children;

FIG. 3 is a graph showing the compression ratio of the Octree;

FIG. 4 is a diagram of examples of a Layered Depth Image (LDI): (a) shows the projection of the object, where the dark cells (voxels) correspond to 1, and the white cells to 0, and (b) shows a two-dimensional section at (x, depth);

FIG. 5 is a diagram showing the color component of the "Angel" model, after recomposing its color data;

FIG. 6 is a diagram showing the orthogonal invariance of the probability of occurrence of the nodes; (a) shows the original current and parent nodes, and (b) shows the current and parent nodes, rotated around the y-axis by 90 degrees;

ES 2 374 064 T3 FIGs. 7, 8 and 9 are geometric compression figures for the procedure based on the best PPM (Portable Map of

Pixels);

FIG. 10 is a diagram showing two ways of recomposing the color field of the Point Texture model of the "Angel" in a two-dimensional image;

FIG. 11 is a diagram of lossless color compression and lossless geometry examples: (a) and (b) are, respectively, the original and compressed versions of the “Angel” model, and (c) and (d) they are, respectively, the original and compressed version of the "Morton256" model;

FIG. 12 is a diagram showing a BVO (Binary Volumetric Octree) and a TBVO (Textured Binary Volumetric Octree) model of the "Angel";

FIG. 13 is a diagram showing additional images taken by additional cameras in the TBVO: (a) is a camera index image, (b) is a first additional image, and (c) is a second additional image;

FIG. 14 is a diagram showing an example of recording a TBVO stream: (a) shows a TBVO tree structure. The color gray is a symbol of "undefined" texture. Each color indicates a camera index, (b) shows the octree traversal order in a BVO node and the camera indices; (c) shows the resulting TBVO stream, in which the padded cubes and the octree cube indicate, respectively, the texture bytes and the BVO bytes;

FIGs. 15, 17, 18 and 19 are diagrams showing, respectively, the TBVO compression results of "Angel", "Morton", "Palmera512" and "Robot512";

FIG. 16 is a diagram showing stripped images of the "Angel" and "Morton" models;

FIG. 20 is a diagram of an example of the texture image and depth map;

FIG. 21 is a diagram of an example Layered Depth Image (LDI): (a) shows Object Projection and (b) shows layered pixels;

FIG. 22 is a diagram of an example Box Texture (BT), in which six Simple Textures (image and depth map pairs) are used to represent the model shown in the center;

FIG. 23 is a diagram of an example Generalized Box Texture (GBT):

(a) shows camera locations for the 'Palm Tree' model, (b) shows reference image planes for the same model (21 SimpleTextures are used);

FIG. 24 is a diagram of an example showing the Octree representation illustrated in 2 dimensions: (a) shows a 'point cloud', (b) shows the corresponding mean maps;

FIG. 25 is pseudo code for recording TBVO bit stream;

FIG. 26 is a diagram showing the specification of DIBR nodes;

FIG. 27 is a view volume model diagram for Image with Depth; (a) is a perspective view, (b) is an orthographic view;

FIG. 28 is pseudocode for the OpenGL-based rendering of SimpleTexture;

FIG. 29 is a diagram of an example showing compression of a reference image in SimpleTexture: (a) shows the original reference image and (b) shows the modified reference image in a JPEG format;

FIG. 30 is a diagram of an example showing the rendering result of the "Morton" model in different formats; (a) is in an original polygonal format, (b) is in a Depth Image format and (c) is in an Octree Image format;

FIG. 31 is a diagram of rendering examples: (a) shows the scanned "Tower" model in a Depth Image format, (b) shows the same model in an Octree Image format (scanner data was used without remove the noise and therefore the black dots in the upper part of the model);

FIG. 32 is a diagram of representation examples of the "Palm Tree" model: (a) shows an original polygonal format and (b) shows the same model, but in a Depth Image format;

FIG. 33 is a diagram of an example representation, showing a plot of the animation of "Dragon512" in

ES 2 374 064 T3

Octárbol Image;

FIG. 34 is a diagram of an example representation of the model "Angel512" in a DotTexture format;

FIGs. 35A and 35B are diagrams showing the relationships of the respective nodes when representing an object in a DepthPicture format, with SimpleTexture nodes and PointTexture nodes, respectively; and FIG. 36 is a diagram showing the structure of the corresponding OctreeImage node when representing an object with OctreeImage nodes.

1. ISO / IEC JTC 1 / SC 29 / WG 11 MOVIE AND AUDIO ENCODING

1. Introduction

In this document, the result of the core experiment on Image-based Rendering, AFX A8.3, is reported. This core experiment is for image-based rendering technology, which uses textures with depth information. Also, based on the experiments after the 57to MPEG meeting and discussions during the AFX Ad Hoc Group meeting in October, there are few changes made to the node specification.

2. Experimental results

2.1. Test models

For fixed objects

DepthImage Node with Simple Texture ♦ Dog ♦ Tyrannosaurus Rex (DepthImage, using about 20 cameras) ♦ Terrasque (a monster) (DepthImage, about 20 cameras) ♦ ChumSungDae (DepthImage, scanned data) ♦ Palm tree (DepthImage, 20 cameras)

Layered Textured Depth Image Node ♦ Angel

DepthImage Node with DotTexture ♦ Angel

Image Node Octree ♦ Creature ♦ For animated objects

Image Node with Depth with Simple Texture ♦ Dragon ♦ Dragon in stage environment

Image Node with Layered Texture Depth ♦ Not indicated

Image Node Octree ♦ Robot ♦ Dragon in stage environment ♦ More data (scanned or modeled) will be provided in the future.

ES 2 374 064 T3

2.2. Test Results • All proposed nodes in Sydney are integrated into the blaxxun contact 4.3 reference software. However, the sources are not yet uploaded to the cvs server.

• IBR animated formats require synchronization between multiple movie files, so images in the same keyframe in each movie file must be rendered at the same time. However, current reference software does not support this synchronization capability, which is possible in MPEG standard systems. Therefore, currently, animated formats can be viewed assuming that all animation data is already in the file. Temporarily, movie files in an AVI format are used for each animated texture.

• After some experimentation with layered textures, we were convinced that the Layered Texture node is not effective. This node was proposed for the Layered Depth Image. However, there is also the PointTexture node that can give you support. Therefore, we propose to remove the Layered Texture node from the node specification. FIG. 1 shows examples of the IBR embedded in current reference software.

3. Updates to the IBR Node Specification

The conclusion of the Sydney meeting on the IBR proposal was to have an IBR stream containing images and camera information, and the IBR node will only have one link (URL) to it. However, during the AhG meeting in Rennes, the result of the IBR debate was to have images and camera information both on the IBR nodes and in the stream. So the following is the updated node specification for IBR nodes. The requirements for the IBR flow are given in the section that explains the URL field.

Decoder (Bit Streams) - Node Specification

ImageWith Depth {

<td>field</td><td>SFVec3f</td><td>position</td><td> 0 0 10</td>

<td>field</td><td>SFRotation</td><td>orientation</td><td> 0 0 1 0</td>

<td>field</td><td>SFVec2f</td><td>field of view</td><td> 0,785389 0,785398</td>

<td>field</td><td>SFFloat</td><td>Flat Close</td><td> 10</td>

<td>field</td><td>SFFloat</td><td>Far plane</td><td> 100</td>

<td>field</td><td>SFBool</td><td>orthogonal</td><td>FALSE</td>

<td>field</td><td>SFNode</td><td>diTexture</td><td>NULL</td>

<td>field</td><td>SFString</td><td>UrlImageWithDepth</td><td></td>

}

The DepthImage node defines a single IBR texture. When multiple DepthImage nodes are related to each other, they are rendered as a group and therefore should be placed under the same Transform node.

The diTexture field specifies the texture with depth, which will be transformed into the region defined in the DepthImage node. It will be one of several types of image textures with depth (SimpleTexture or DotTexture).

The position and orientation fields specify the relative location of the IBR texture viewpoint in the local coordinate system. Position is relative to the origin (0, 0,0) of the coordinate system, while orientation specifies a rotation relative to the default orientation. In the default position and orientation, the viewer is on the Z axis, looking down the Z axis, toward the origin, with positive Xs to the right and positive Ys facing up. However, the transformation hierarchy affects the final position and orientation of the point of view.

The fieldOfVision field specifies an angle of view from the camera's point of view, defined by position and orientation fields. The first value indicates the angle with the horizontal side and the second value indicates the angle with the vertical side. The default values are 45 degrees in radians. However, when the orthogonal field is set to TRUE, the visionField field indicates the width and height of the near plane and the far plane.

The Near Plane and Far Plane fields specify the distances from the viewpoint to the near plane and the far plane of the visibility area. Texture and depth data show the area enclosed by the plane

ES 2 374 064 T3 near, far plane and fieldOfVision. The depth data is normalized for the distance from the

Near Plane to Far Plane.

The orthogonal field specifies the type of view of the IBR texture. When set to TRUE, the IBR texture is based on the orthogonal view. Otherwise, the IBR texture is based on perspective view.

The DepthImageUrl field specifies the direction of the flow of images with depth, which can optionally contain the following content.

* position * orientation * visionField * NearPlane * FarPlane * orthogonal * diTexture (SimpleTexture or PointTexture) * 1-octet header for the active / inactive indicators of the previous fields

SimpleTexture {SFNode field NULL texture SFNode depth NULL field}

The SimpleTexture node defines a single layer of IBR texture.

The texture field specifies the flat image that contains color for each pixel. It will be one of several types of texture nodes (ImageTexture, FilmTexture, or PixelTexture).

The depth field specifies the depth for each pixel in the texture field. The size of the depth map will be the same size as the image or movie in the texture field. It will be one of several types of texture nodes (ImageTexture, FilmTexture, or PixelTexture). If the depth node is NULL, or if the depth field is not specified, the alpha channel in the texture field will be used as the depth map.

PointTexture {

<td>field</td><td>SFInt32</td><td>broad</td><td> 256</td>

<td>field</td><td>SFInt32</td><td>tall</td><td> 256</td>

<td>field</td><td>MFInt32</td><td>depth</td><td> []</td>

<td>field</td><td>MFColor</td><td>Colour</td><td> []</td>

}

The PointTexture node defines multiple layers of IBR points.

The width and height fields specify the width and height of the texture.

The depth field specifies multiple depths of each point (in normalized coordinates) on the projected plane in the order of the path, starting from the point in the lower left corner and proceeding to the right to end the horizontal line before advancing to the top line. For each point, the number of depths (pixels) is stored first, and that number of depth values will follow.

The color field specifies the color of the current pixel. The order will be the same as the depth field, except that the number of depths (pixels) for each point is not included.

ES 2 374 064 T3

ImagenOctárbol {

<td>field</td><td>SFInt32</td><td>resolution octree</td><td> 256</td>

<td>field</td><td>SFString</td><td>octree</td><td></td>

<td>field</td><td>MFNode</td><td>images october</td><td> []</td>

<td>field</td><td>SFString</td><td>URLocttree</td><td> “”</td>

}

The OctreeImage node defines an octree structure and its projected textures. The size of the surrounding cube of the total octree is 1 x 1 x 1, and the center of the cube of the octree will be the origin (0, 0, 0) of the local coordinate system.

The octreeresolution field specifies the maximum number of leaves of the octree along one side of the surrounding cube. The octree level can be determined from octreeresolution, using the following equation: octareelevel = ent (log2 (octreeresolve-1)) + 1)

The octree field specifies a set of internal nodes of the octree. Each internal node is represented by one octet. A 1 in the i-th bit of this octet means that child nodes exist for the i-th child of that inner node, while 0 means that they do not exist. The order of the internal nodes of the octree will be the amplitude order of the first traversal of the octree. The order of eight children of an internal node is shown in FIG. 2.

The octreeimages field specifies a set of DepthImage nodes with SimpleTexture for the diTexture field. However, the NearPlane and FarPlane fields of the DepthImage node and the depth field of the Simple Texture node are not used.

The October_URL field specifies the direction of the NightTree Image stream with the following content.

* header for indicators * octree resolution * octree * octree images (Multiple ImageWith Depth nodes)

Flat Close Not Used

Farplane not used diTexture -> SimpleTexture without depth

II. ISO / IEC JTC 1 / SC 29 / WG 11 MOVIE AND AUDIO ENCODING

1. Introduction

In this document, the result of the core experiment on Depth Imaging Based Rendering (DIBR), AFX A8.3, is reported. This core experiment is for depth image-based rendering nodes, which use textures with depth information. The nodes have been accepted and included in a proposal for the Committee Draft during the Pattaya meeting. However, the flow of this information through the OCTreeURL field of the OCTreePicture node and the URLImageWithDepth field of the DepthImage node was still going. This document describes the format of the flow to be linked by these URL fields. The stream format includes the compression of the octree field of the OctreeImage node and the depth / color fields of the PointTexture node.

2. Stream format for URLocttree

2.1. Stream format

The OctreeImage node includes the OctreeURL field, which specifies the direction of the OctreeImage stream. This stream can optionally contain the following content.

* header for indicators * octree resolution

ES 2 374 064 T3 * octree * octreeimages (Multiple nodes of ImageWith Depth)

Flat Close Not Used

Farplane not used diTexture -> - SimpleTexture without depth

The octree field specifies a set of internal octree nodes. Each internal node is represented by one octet. A 1 in the i-th bit of this octet means that there are child nodes for the i-th child of that inner node, while a 0 means that they do not exist. The order of the internal nodes of the octree will be the order of travel, of amplitude first, of the octree. The order of eight children of an internal node is shown in FIG. 2.

The octree field of the OctreeImage node is in a compact format. However, this field can be further compressed in order to have efficient flow. The following section describes the compression scheme for the octree field of the OctreeImage node.

2.2. Compression scheme for the octree field

In the octree representation of the DIBR, the data consists of the octree field, which represents the geometry component. The octree is a set of points on the surrounding cube, which fully represent the surface of the object.

The non-identical reconstruction of the geometry from the compressed representation leads to extremely remarkable visual effects. Therefore, the geometry must be compressed without loss of information.

2.2.1. Octree compression

For the compression of the octree field, represented as a depth traversal octree first, we developed a lossless compression procedure, using some ideas from the PPM (Partial Match Prediction) approach. The main idea we use is the "prediction" (ie the probability estimate) of the next symbol by several previous symbols, which are called the "context". For each context, there is a probability table, which contains the estimated probability of occurrence of each symbol in this context. This is used in combination with an arithmetic encoder called a distance encoder.

The two main characteristics of the procedure are:

1. use of a parent node as a context for the child node;

2. use of an 'orthogonal invariance' hypothesis to reduce the number of contexts.

The second idea is based on the observation that the 'transition probability' for pairs of 'parent-child' nodes is usually invariant by orthogonal transforms (rotation and symmetry). This hypothesis is illustrated in Appendix 1. This hypothesis allows us to use a more complex context without having too many probability tables. This, in turn, allowed us to achieve quite good results in terms of volume and speed, because the more contexts that are used, the more accurate the probability estimate, and therefore the more compact the code.

Coding is the process of building and updating the probabilistic table according to the context model. In the proposed procedure, the context is modeled as the parent-child hierarchy in the octree structure. First, we define the Symbol as a node of octets whose bits indicate the occupation of the subcube after the internal subdivision. Therefore, each node in the octree can be a symbol and its numerical value will be between 0 and 255. The probabilistic table (PT) contains 256 integer values. The value of the ith variable (0 <i <255), divided by the sum of all the variables, is equal to the frequency (probability estimate) of the occurrence of the ith symbol. The Probabilistic Context Table (PCT) is a set of PTs. The probability of a symbol is determined from one and only one of the PTs. The specific PT number depends on the context. An example of PCT is shown in Table 1.

ES 2 374 064 T3

Table 1. Component of a Probabilistic Context Table (PCT)

<td>PT identifier</td><td> 0</td><td> 1</td><td></td><td> 255</td><td>Context description</td>

<td> 0</td><td>P0.0</td><td>P0,1</td><td></td><td>P0,255</td><td>Context-0: independent of context</td>

<td> 1..27 (27)</td><td>Pi, 0</td><td>Pi, 1</td><td></td><td>P i, 255</td><td>Context-1: Parent Symbol</td>

<td> 28...243 (27*8)</td><td>Pj, 0</td><td>Pj, 1</td><td></td><td>Pj, 255</td><td>Context-2: Parent Symbol and Node Symbol</td>

The encoder works as follows. It first uses the 0-context model (that is, a single PT for all symbols, starting from the uniform distribution, and updating the PT after each new encoded symbol). The tree is traversed in depth order first. When enough statistics have been gathered (the empirically found value is 512 coded symbols), the encoder switches to the context model-1. It has 27 contexts, which are specified according to the following.

Consider a set of 32 fixed orthogonal transforms, which include symmetries and 90 degree rotations around the coordinate axes (see Exhibit 2). So we can categorize the symbols based on the fill pattern of their subcubes. In our procedure, there will be 27 sets of symbols, here called groups, with the following property: 2 symbols are connected by one of these fixed transforms if and only if they belong to the same group.

In octet notation, groups are represented by 27 sets of numbers (see Annex 2). We assume that the probability table depends not on the parent node itself (in which case, there would have been 256 tables), but only on the group (indicated as ParentSymbol in FIG. 2) to which the parent node belongs (thus, 27 tables ).

At the time of switching, the PTs for all contexts are set to copies of the PT of context-0. Then each of the 27 PTs is updated when used for encoding.

After 2,048 (another heuristic value) symbols are encoded in the context-1 model, we switch to the context-2 model, which uses the pairs (Parent Symbol, Node Symbol) as contexts. The NodeSymbol is simply the position of the current node in the parent node. Then we have 27 * 8 contexts for the context-2 model. At the moment of switching to that model, the PTs obtained for each context are used for each node 'within' this context, and from this moment they are updated independently.

In some more technical detail, the coding for the context-1 and context-2 models is developed as follows. For the context of the current symbol (that is, the parent node), its group is determined. This is done by table search (the geometric analysis was carried out in the development stage of the program). Then, we apply an orthogonal transform that takes our context to a “standard” element (arbitrarily selected once and for all) of the group to which it belongs. The same transform applies to the symbol itself (these operations are also implemented as table lookup, of course - all calculations for all possible combinations were done in advance). Effectively, this is the calculation of the correct position of the current symbol in the probability table for the group that contains its context. Then the corresponding probability is supplied to the DistanceCoder.

In short, given a parent symbol and subnode position, the ContextIdentifier is determined, which identifies the Group Identifier and the position of the PT in the PCT. The probability distribution in the PT and the ContextIdentifier are supplied to a distance encoder. After encoding, the PCT is updated for use in the next encoding. Note that the distance encoder is a variation of arithmetic encoding, renormalizing in octets rather than bits, thus operating twice as fast, and with compression 0.01% worse than a standard implementation of the arithmetic coding.

The decoding process is essentially a reversal of the encoding process. This is an absolutely standard procedure that does not need to be described, since it uses exactly the same procedures for determining contexts, updating probabilities, etc.

2.3. Test results

FIG. 3 is a table for the comparison of our approach, for both fixed and animated models (the ordinates indicate the compression ratio). The octree compression ratio varies around 1.5 to 2 times compared to the original size of the octree, and outperforms general purpose lossless compressions (based on Lempel-Ziv, such as RAR program) in up to 30%.

ES 2 374 064 T3

3. Stream Format for ImageDepth URL

3.1. Stream format

The ImageWith Depth node includes the URLImageWithDepth field, which specifies the direction of the flow of images with depth. This stream can optionally contain the following content.

* 1 octet header for the on / off indicators of the fields below * position * orientation * VisionField * NearPlane * FarPlane * orthogonal * diTexture (SimpleTexture or PointTexture)

The definition of the PointTexture node, which can be used in the diTexture field of the DepthImage node, is as follows.

PointTexture {

<td>field</td><td>SFInt32</td><td>broad</td><td> 256</td>

<td>field</td><td>SFInt32</td><td>height</td><td> 256</td>

<td>field</td><td>MFInt32</td><td>depth</td><td> []</td>

<td>field</td><td>MFColor</td><td>Colour</td><td> []</td>

}

The PointTexture node defines multiple layers of IBR points. The width and height fields specify the width and height of the texture. The depth field specifies multiple depths of each point (in normalized coordinates) on the projected plane in the order of travel, starting from the point in the lower left corner and proceeding to the right to end the horizontal line before advancing to the top line. For each point, the number of depths (pixels) is stored first, and that number of depth values will come later. The color field specifies the color of the current pixel. The order will be the same as the depth field, except that that number of depths (pixels) is not included for each point.

The depth and color fields of the PointTexture are in raw format, and the size of these fields will most likely be very large. Therefore, these fields must be compressed in order to have efficient flow. The following section describes the compression scheme for the fields of the PointTexture node.

3.2. Compression scheme for PointTexture

3.2.1. Depth field compression

The depth field of the PointTexture node is simply a set of points in a 'discretized surrounding cube'. We assume that the lower plane is the projection plane. Given the grids of dimension m * n * l for a model, being points the centers of the cells (in the case of the octree, we call them voxels) of this grid, we can consider the occupied voxels as the 1s and the empty voxels as the 0. The resulting set of bits (m * n * l bits) is then organized into a stream of octets. This is done by traversing the voxels in the depth direction (orthogonal to the projection plane), in layers of depth 8, and in the usual order (“by columns”) in the projection plane (filling, if necessary, the last octet layer with zeros in case the depth dimension is not a multiple of 8). Thus, we can think of our point set as a stack of 8-bit grayscale images (variant: 16-bit images). The voxel and bit mapping is illustrated in FIG. 4 (a).

For example, in FIG. 4 (b), the black squares correspond to the points on the object. The horizontal plane is the projection plane. Consider the 'slice' at height 16 (its upper limit is shown in thick lines). Let's interpret the 'columns' as octets. That is, a column above the point marked in the figure represents the stack of 2

ES 2 374 064 T3 octets, with values 18 and 1 (or a 16-bit unsigned 274 integer). If we apply the best available PPM-based compression procedures to the octet union obtained in this way, we get quite good results. However, if a simple context-1 procedure is applied directly here (no orthogonal, or hierarchical invariance context can be used here, of course), this results in a slightly lower degree of compression. Here is a table of volumes required for different types of LDI geometry representations: BVOC, the previous array of bytes compressed by the best PPM compressor, and the same array compressed by our currently used compressor (figures in Koctets).

<td>Model</td><td>BVOC representation of geometry</td><td>Better PPM compression of byte formation</td><td>Simple context-1 compression of octet formation</td>

<td>"Angel"</td><td> 31,4</td><td> 27,5</td><td> 32</td>

<td>"Morton"</td><td> 23,4</td><td> 23,3</td><td> 30,5</td>

<td>"Grasshopper"</td><td> 16,8</td><td> 17,0</td><td> 19,7</td>

3.2.2. Color field compression

The color field of the PointTexture node is a set of colors attributed to points in the object. Unlike the case of the octree, the color field is in one-to-one correspondence with the depth field. The idea is to represent color information as a single image, which could be compressed by one of the known lossy techniques. The cardinality of this image is much smaller than that of the reference images in the octree or in the case of the DepthImage, and is an essential motivation for such an approach. The image can be obtained by traversing the depth points in this or that natural order.

Let's first consider the scan order dictated by our original storage format for LDI (PointTexture) - 'depth-first' scan of the geometry. The multipixels are traversed in the natural order along the projection plane, as if they were single pixels, and the points within the same multipixel traverse in the direction of depth. This scan order produces a one-dimensional array of colors (1st non-zero multipixel, 2nd non-zero multipixel, etc.). As soon as the depth is known, the colors of the points can be successively reconstructed from this formation. To make the image compression procedures applicable, we must uniquely associate this long chain with the two-dimensional array. This can be done in many ways.

The approach used in testing below is the so-called "block scan", when the color chain is arranged in 8 * 8 blocks, and those blocks are arranged in columnar order ("block scan"). The resulting image is shown in FIG. 5.

The compression of this image was carried out by various procedures, including the JPEG standard. It turns out that at least for this type of color scan, much better results are obtained using the texture compression procedure described in [5]. This procedure is based on the adaptive local palletization of each 8 * 8 block. It has two modes: 8 and 12 compression (compared to 24 bit per pixel true color 'raw' BMP format). The success of this procedure in this type of images can be explained exactly from its character of palette, which allows us to take into account sharp local variations (even non-borderline ones!) Of color, which arise from the 'mixture' of the points on the front and back surfaces (which can differ greatly, as in the case of the “Angel”). The goal of finding the optimal scan is to reduce these variations as much as possible.

3.3. Test results

Examples of models in the original and compressed formats are shown in Annex 3. The quality of some models (eg Angel) is still not quite satisfactory after compression, while others are very good ('Grasshopper '). However, we feel that this problem can be solved with the help of a proper scan. Potentially even the 12-by-compression mode could be used, so the overall compression increases further. Finally, lossless compression will improve to approximate the best PPM-based results in geometric compression.

Here we give a table of compression ratios.

ES 2 374 064 T3

<td>Model</td><td>Reason for the best PPM procedure</td><td>Reason for simple context-1 procedure</td>

<td>"Angel"</td><td> 7,1</td><td> 6,7</td>

<td>"Morton"</td><td> 7,5</td><td> 6,7</td>

<td>"Grasshopper"</td><td> 7,8</td><td> 7,4</td>

Four. Conclution

In this document, the result of the core experiment on Image-Based Depth Rendering, AFX A8.3, is reported. The DIBR flow has been introduced, which is linked through the URL fields of the DIBR nodes. These flows consist of all the items in the DIBR node, along with a flag for each item, to make it optional. In addition, the compression of the octree and that of the PointTexture data are investigated.

Annex 1. Geometric meaning of the orthogonal invariance of the context in the BVO compression algorithm.

The orthogonal invariance hypothesis is illustrated in FIG. 6. Consider the rotation around the vertical axis by 90 degrees clockwise. Consider the arbitrary padding patterns of the node and its parent before (top image) and after rotation (bottom image). Then two different patterns can be treated as the same pattern.

Annex 2. Groups and Transformed.

1. 32 fixed orthogonal transforms.

Each transform is specified by a 5-bit word. The bit combination is the composition of the following basic transforms (that is, if the k-th bit is 1, the corresponding transform is performed)

1st bit - permute x and y coordinates;

2nd bit - swap yyz coordinates;

3rd bit - symmetry in the plane (yz);

4th bit - symmetry in the (xz) plane;

5th bit - symmetry in the (xy) plane;

2. 27 groups.

For each group, here is the order of the group and the number of non-null bits in its elements: NumberOfGroup, NumberOfGroups, and NumberOfFillBits (VoxelsSet).

<td>Group</td><td>Group order (number of elements)</td><td>Number of non-zero bits in each element of the group</td>

ES 2 374 064 T3

3. Symbols and transforms.

For each symbol (s), here is the index of the group (g) it belongs to and the value of the transform (t) that takes it to the 'standard' element of the group.

The binary number of the symbol is associated with the binary coordinates of voxel as follows: the i-th bit of the number has binary coordinates x = i & 1, y = i & (1 << 1), <= i & (1 << 2 ).

ES 2 374 064 T3

Annex 3. PointTexture compression screenshots.

In FIGs. 7, 8 and 9, the geometric compression figures are given for the best PPM-based procedure.

III. Result of the core experiment on Image-Based Depth Representation (AFX A8.3)

1. Introduction

In this document, the result of the core experiment on Depth-Based Imaging (DIBR), AFX A8.3, is reported. This core experiment is for image-based depth rendering nodes that use textures with depth information. The nodes have been accepted and included in a proposal for the Committee Draft during the Pattaya meeting. However, the flow of this information through the OctreeImage node and the DepthImage node were still in process. This document describes the format of the flow to be linked by these nodes. The stream format includes the compression of the octree field of the OctreeImage node and the depth / color fields of the PointTexture node.

2. DIBR format compression

We describe here a novel technique for efficient lossless compression of a linkless octree data structure, which enables a reduction in the volume of this already compact representation of about 1.5 to 2 times in our experiments. We also suggest several techniques for lossless and lossy compression of the PointTexture format, using an intermediate representation of voxel in combination with entropy encoding and the specialized block-based texture compression procedure [6].

2.1. Image Compression Octree

The octree and octree image fields in Octree Image are compressed separately. The procedures described have been developed based on the notion that the octree field should be compressed losslessly, while allowing some degree of visually acceptable distortion for octree images. The octree image field is compressed by means of the image compression of the MPEG-4 standard (for the static model), or by video compression tools (for the animated model).

2.1.1. Octree field compression

Octree compression is the most important part of OctreeImage compression, as it deals with compressing an already very compact representation of an unlinked binary tree. However, in our experiments, the procedure explained below reduced the volume of this structure to almost half of the original. In the animated version of OctreeImage, the Octree field is compressed separately for each three-dimensional frame.

2.1.1.1. Context model

Compression is done by a variant of adaptive arithmetic encoding (implemented as a 'distance encoder') that makes explicit use of the geometric nature of the data. The Octree is a stream of bytes. Each octet represents a node (ie, subcube) of the tree, in which its bits indicate the occupation of the subcube after internal subdivision. The bit pattern is called the node fill pattern. The described compression algorithm processes the bytes one by one, as follows.

* A context is determined for the current octet.

* retrieve the 'probability' (normalized frequency) of occurrence of the current octet in this context from the 'probability table' (PT) corresponding to the context.

* The probability value is supplied to the distance encoder.

* The current PT is updated by adding 1 to the frequency of occurrence of the current octet in the current context (and, if necessary, renormalized later; see details below).

Thus, coding is the process of building and updating PTs according to the context model. In context-based adaptive arithmetic coding schemes (such as 'Partial Match Prediction'), the context of a symbol is usually a string of several preceding symbols. However, in our case, the efficiency of compression is increased by exploiting the structure of the octree and the geometric nature of the data. The approach described is based on two ideas that are apparently new to the octree compression problem.

A. For the current node, the context is either its parent node, or the pair {parent node, current position of node at parent node};

ES 2 374 064 T3

B. The 'probability' of the occurrence of a given node at the specific geometric location at the specific parent node is assumed to be invariant with respect to a certain set of orthogonal transforms (such as rotations or symmetries).

Hypothesis 'B' is illustrated in FIG. 6, for the transform R, which is the rotation by -90 ° in the xz plane. The basic notion behind 'B' is the observation that the probability of occurrence of a specific type of child node at a specific type of parent node should depend only on its relative position. This hypothesis is confirmed in our experiments, by the analysis of probability tables. It allows us to use a more complex context, without having too many probability tables. This, in turn, helps achieve pretty good results in terms of data size and speed. Note that the more contexts that are used, the more accurate the estimated probability and, therefore, the more compact the code.

Let us introduce the set of transforms for which we will assume the invariance of probability distributions. In order to apply to our situation, such transforms should preserve the surrounding cube. Let us consider a set G of orthogonal transforms in Euclidean space, which are obtained by all compositions, in any number and order, of the 3 basic transforms (generators) m2 and m3, given by

where n and m2 are reflections on the planes x = y and y = z, respectively, and m3 is the reflection on the plane x = 0. One of the classic results of reflex-generated group theory states that G contains 48 different orthogonal transforms, and is, in a sense, the largest group of orthogonal transforms that convert the cube into itself (the so-called Coxeter group). For example, the rotation R in FIG. 1 is expressed, by means of generators, as

R = m3 m2 πη m2 where '·' is matrix multiplication.

The G transform, applied to an octree node, produces a node with a different subcube fill pattern. This allows us to categorize the nodes according to the fill pattern of their subcubes. Using the language of group theory, we say that G acts on the set of all padding patterns of the nodes of the octree. Calculations show that there are 22 distinct classes (also called orbits in group theory), in which, by definition, two nodes belong to the same class if, and only if, they are connected by a G transform. The number of Elements in a class ranges from 1 to 24, and is always a divisor of 48.

The practical consequence of 'B' is that the probability table depends not on the parent node itself, but only on the class to which the parent node belongs. Note that there would be 256 tables for a context based on parents and some 256x8 = 2048 additional tables for a context based on the position of parent and child in the previous case, while we only need 22 tables for the context based on the parent's class, plus 22x8 = 176 tables in the last case. Therefore, it is possible to use an equivalently complex context with a relatively small number of probability tables. The constructed PT would have the form shown in Table 2.

Table 2. Enumeration of probability tables.

<td>PT identifier</td><td> 0</td><td> 1</td><td></td><td> 255</td><td>Context description</td>

<td> 0</td><td>P0.0</td><td>P0.1</td><td></td><td>P0.255</td><td>Context-0: Independent of context</td>

<td> 1..22(22)</td><td>Pi, 0</td><td>Pi, 1</td><td></td><td>P, 255</td><td>Context-1: {parent node class}</td>

<td> 23..198(176)</td><td>Pj, 0</td><td>Pj, 1</td><td></td><td>Pj, 255</td><td>Context-2: {class of parent node, current position of node}</td>

2.1.1.2. Encoding process

To make the statistics for probability tables more accurate, they are collected in different ways in three stages of the coding process.

ES 2 374 064 T3 * In the first stage we do not use contexts at all, accepting the 'context-0 model', and we maintain a single probability table with 256 entries, based on the uniform distribution;

* As soon as the first 512 nodes are encoded (it is an empirically found number), we switch to the 'context model-1', using the parent node as a context. At the time of switching, the PT of context-0 is copied to PTs for all 22 contexts.

* After 2,048 nodes have been coded (another heuristic value), we switch to 'context model-2'. At this time, the context-1 PTs of the parent patterns are copied to the PTs for each position in the same parent pattern.

The key point of the algorithm is the determination of the context and the probability for the current octet. This is implemented as follows. In each class we set an individual element, which is called 'standard element'. We store a class map table (CMT) that indicates the class to which each of the possible 256 nodes belongs, and the precomputed transform of G that takes this specific node to the standard element of its class. Thus, in order to determine the probability of the current node N, we carry out the following steps:

* Look at the parent P of the current node;

* Retrieve the class of the CMT, to which P belongs, and the transform T that takes P to the standard node of the class.

* Let c be the class number;

* Apply T to P and find the position p of the child in the standard node to which the current node N is associated;

* Apply T to N. Then, the newly obtained fill pattern TN is at position p at the standard node of class c.

* Retrieve the required probability from the TN entry of the probability table corresponding to the combination (c, p) of class and position.

For the context-1 model, the previous stages are obviously modified. It goes without saying that all transforms are precomputed and implemented in a lookup table.

Note that in the decoding stage of node N, its parent P is already decoded and therefore the transform T is known. All the stages in the decoding stage are absolutely similar to the corresponding encoding stages.

Finally, let's outline the probabilities update process. Let P be a table of probabilities for some context. Let us indicate with P (N) the entry of P corresponding to the probability of occurrence of node N in this context. In our implementation, P (N) is an integer, and after each occurrence of N, P (N) updates as:

P (N) = P (N) + A, where A is an integer incremental parameter that usually ranges from 1 to 4 for different context models. Let S (P) be the sum of all the inputs in P. Then the 'probability' of N supplied to the arithmetic encoder (distance encoder in our case) is calculated as P (N) / S (P). As soon as S (P) reaches a threshold value 216, all the inputs are renormalized: in order to avoid the occurrence of zero values in P, the inputs equal to 1 are left intact, while the others are divided by 2.

2.2. PointTexture Compression

The PointTexture node contains two fields to compress, that is, depth and color. The main difficulties in compressing PointTexture data are due to the following requirements:

* Geometry must be compressed so that it is lossless, as distortions in this type of geometric representation are often extremely noticeable.

* Color information does not have any natural two-dimensional structure and therefore image compression techniques are not immediately applicable.

In this section we suggest three procedures for compression of the PointTexture model:

* Lossless procedure for standard node representation.

* Lossless procedure for the lower resolution representation of the node.

* Lossless geometry and lossy color compression for lower resolution rendering of the node.

ES 2 374 064 T3

The procedures correspond to the three levels of 'fidelity' of the object description. The first procedure assumes that we should store the depth information down to its original 32-bit precision. However, in practice, depth information can often be quantized to a much smaller number of bits, without loss of quality. In particular, when the PointTexture model is converted from the polygonal model, the resolution of the quantization is chosen according to the effective size of the visible details that the original model has, as well as the desirable resolution of the output screen. In this case, between 8 and 11 bits may well satisfy the requirements, and the depth values are initially stored in this lower resolution format. Now our second procedure deals with lossless compression of this 'lower resolution' representation. The key observation here is that, for such a relatively small number (compared to the standard 32) of bits, an intermediate voxel representation of the model can be used, allowing us to compress the depth field, essentially without loss of information. The color information in both cases is losslessly compressed and stored in a PNG format, after rearranging the color data as an auxiliary two-dimensional image.

Finally, the third procedure allows us to achieve much higher compression, combining lossless compression of geometry with lossy compression of color data. The latter is done by a specialized block-based texture compression technique. The following three subsections describe the procedures in full detail.

2.1.1. Lossless PointTexture compression for standard node representation

This is a simple lossless encoding procedure, which works as follows.

* The depth field is compressed by the adaptive distance encoder, similar to that used in Octreek field compression. For this format, we use a version in which the probability table is maintained for each of the 1-symbol contexts, and the context is simply the previous octet. Therefore, 256 PTs are used. The depth field is considered as a stream of octets, and the geometric structure is not used explicitly.

* The color field is compressed after conversion to a true color flat image. The colors of the points in the PointTexture model are first recorded in a temporary one-dimensional array, in the same order as the depth values in the depth field. If the total number of points in the model is L, then we calculate the smallest integer I such that I · I> L, and 'fold' this long 'chain' of color values into the square image of side I (if it is necessary, filling with black pixels). This image is then compressed with one of the lossless image compression tools of the MPEG-4 standard. In our approach, we use a Portable Network Graphics (PNG) format. The image obtained in this way from the 'Angel' model is shown in FIG. 10 (a).

2.2.2. Lossless PointTexture compression for lower resolution rendering of node

In many cases, the 16-bit resolution for depth information is excessively fine. In fact, the resolution in depth should correspond to the resolution of the screen on which the model is to be displayed. In situations where small variations in the depth of the model at different points lead to a displacement in the screen plane much smaller than the pixel size, it is reasonable to use a lower resolution in depth, and the models are often rendered in the A format in which the depth values occupy between 8 and 11 bits. Such models are usually obtained from other formats, eg. eg, the polygonal model, discretizing the depth and color values in the appropriate spatial grid.

Such a reduced resolution representation can itself be considered a compressed form of the 32-bit depth standard model. However, there is a more compact representation for such models, using the voxel intervening space. Indeed, it can be assumed that the model points belong to uniform spatial grid nodes, with the spacing determined by the discretization step. We can always assume that the grid is uniform and orthogonal, since, in the case of the perspective model, we can work in the parametric space. Using this observation, the depth and color fields of the lower resolution DotTexture are compressed as follows.

* the color field is compressed using a lossless image compression technique, as in the previous procedure;

* the depth field is first transformed to voxel representation, and then compressed by the variant of the distance encoder described in the previous subsection.

The intermediate voxel model is constructed as follows. According to the resolution s depth of the model, consider the discrete voxel space of size width x height x 23 (The 'width' and 'height' parameters are explained in the PointTexture specification). For our purposes, we do not need to work with a potentially huge voxel space as a whole, but only with its 'thin' cross sections. Let us indicate with (r, c)

ES 2 374 064 T3 the model row and column coordinates in the projection plane, and let d be the depth coordinate. We transform the 'slices' {c = constant}, that is, the cross sections of the model by 'vertical planes', in the representation by voxels. Traversing the slice along the 'columns' parallel to the projection plane, we set the voxel (r, c, d) to 'black' if and only if there is a point in the model with a depth d value that is projected on (r, c). The process is illustrated in FIG. Four.

As soon as the slice is built, it is compressed by the context distance encoder-1, and compression of the next slice begins. In this way, we avoid working with very large formations. The probability tables are not initialized for each new slice. For a wide range of models only a small fraction of the voxels are black, and this allows us to achieve a fairly high compression ratio. The decompression is effected by the obvious reversal of the operations described.

The comparison between depth field compression by this procedure and by octree representation will be described. The overall compression ratio of the model is determined, however, by the color field, since such an irregular image cannot be extremely compressed without distortion. In the next subsection we consider a combination of lossless geometry and lossy color compression technique.

2.2.3. Lossless geometry and lossy color compression for lower resolution DotTexture rendering

Like the previous one, this procedure transforms the depth field into the representation by voxels, which is then compressed by the adaptive encoder of context distances-1. The color field is also associated with the two-dimensional image. However, we make an attempt to organize the association such that points that are close in three-dimensional space are associated with close points on the two-dimensional image plane. Then a specialized texture compression procedure (Adaptive Block Partitions, ABP) is applied to the resulting image. The main stages of the algorithm are as follows.

1. Transform a 'slice' of four successive 'vertical planes' of the PointTexture model into voxel representation.

2. Scan the formation obtained from voxels of dimensions width x 4 x 25:

* Traversing the vertical 'plane' of 4 x 4 x 4 voxel subcubes along the 'columns' parallel to the projection plane: first the column closest to the projection plane, then the next closest column, etc. (that is, in the usual order of travel of two-dimensional formations).

* Traversing the voxels within each 4x4x4 subcube in the order analogous to that used in tracing the subcubes of OctreeImage nodes.

3. Record the colors of the points of the model found in this order of travel, in an auxiliary one-dimensional formation;

Four. Rearrange the obtained color formation in a two-dimensional image, so that:

5. 64 consecutive color samples are arranged, by columns, in an 8-by-8 pixel block, 64 subsequent samples are arranged in the adjacent 8-by-8 pixel block, and so on.

6. Compress the image obtained by the ABP technique.

This procedure of scanning a three-dimensional array and transforming the result into the two-dimensional image was chosen from the following considerations. Note that the 4x4x4 subcubes and the 8x8 image blocks contain the same number of samples. If several successively scanned subcubes contain enough color samples to fill the 8x8 block, it is highly likely that this block is fairly uniform and therefore the distortion will be barely discernible in the three-dimensional model after decompression. The ABP algorithm compresses 8x8 blocks independently of each other, with the help of local palletizing. In our tests, the distortion introduced by ABP compression in the final three-dimensional model was drastically less than that of the JPEG standard. Another reason for choosing this algorithm was the high decompression speed (for which it was originally designed). The compression ratio can take two values, 8 and 12. In the PointTexture compression algorithm, we set the compression ratio to 8.

Unfortunately, this algorithm is not universally applicable. Although the image obtained in this way from the color field, shown in FIG. 10 (b), is much more uniform than for 'natural' scan order, sometimes 8x8 two-dimensional blocks can contain color swatches corresponding to distant points in three-dimensional space. In this case, the lossy ABP procedure can 'mix' colors from different parts of the model, leading to local but noticeable distortion after decompression.

ES 2 374 064 T3

However, for many models, the algorithm works very well. In FIG. 11, we show the 'bad' case ('Angel' model) and the 'good' case ('Morton256' model). The reduction of the volume of the model in both cases is around 7 times.

3. Test results

In this section we compare the compression results of two models, 'Angel' and 'Morton256', in two different formats: OctreeImage and PointTexture. The dimensions of the reference images for each model were 256x256 pixels.

3.1. PointTexture Compression

In Tables 3 to 5, the results of different compression procedures are given. The models for this experiment were derived from models with an 8-bit depth field. Depth values expanded over the range (1, 230), using quantization step 221+1, in order to make the distribution of the bits in the 32-bit depth values more uniform, somewhat mimicking the 'true' 32-bit values.

No major compression ratios are to be expected from this procedure. The volume reduction is of the same order as for typical lossless compression of true color images. The compressed depth and color fields are of fairly comparable size, as the geometric nature of the data is not captured by this approach.

Now let's see how much the same models can be losslessly compressed when shot at their 'true' depth resolution. Unlike the previous case, the depth field is losslessly compressed about 5 to 6 times. This is due to the intermediate representation by voxels that makes the geometric redundancy of the data much more pronounced: indeed, only a small fraction of the voxels are black. However, since the uncompressed size of the models is smaller than for the 32-bit case, the compression ratio of the color field now determines the overall compression ratio, which is even smaller than for the 32-bit case. (although the output files are also smaller). Next, it is desirable to be able to compress the color field at least as well as the depth field.

Our third procedure uses the lossy compression technique called ABP [6] for this purpose. This procedure gives a much greater compression. However, like all lossy compression techniques, it can lead to nasty distortions in some cases. An example of an object for which this occurs is the 'Angel' model. In the process of scanning the model points, spatially distant points sometimes fall into the same two-dimensional image block. Colors at distant points on this model can differ greatly, and local palletizing cannot provide an exact approximation if there are too many different colors in a block. On the other hand, it is the local palletization that allows us to accurately compress a vast majority of the blocks, for which the distortion introduced by, say, the JPEG standard becomes absolutely unbearable after the reconstructed colors are repositioned. three-dimensional. However, the visual quality of the 'Morton256' model compressed by the same procedure is excellent, and this was the case for most of the models in our experiments.

Table 3. Lossless PointTexture Compression for 32-bit Depth Field (In Bytes).

<td colspan="2" rowspan="2">Model</td><td rowspan="2">depth field</td><td rowspan="2">color field</td><td rowspan="2">Overall size</td><td colspan="3">Compression ratio</td>

<td>Depth</td><td>Colour</td><td>Total</td>

<td rowspan="2">"Morton256"</td><td>Original</td><td> 691.032</td><td> 321.666</td><td> 1.012.698</td><td rowspan="2"> 3,1</td><td rowspan="2"> 1,2</td><td rowspan="2"> 2,0</td>

<td>Compressed</td><td> 226.385</td><td> 270.597</td><td> 424.562</td>

<td rowspan="2">"Angel"</td><td>Original</td><td> 665.488</td><td> 302.508</td><td> 967.996</td><td rowspan="2"> 3,3</td><td rowspan="2"> 1,2</td><td rowspan="2"> 2,1</td>

<td>Compressed</td><td> 204.364</td><td> 262.209</td><td> 466.604</td>

ES 2 374 064 T3

Table 4. PointTexture Lossless Compression for Lower Resolution Node Representation (In Bytes).

<td colspan="2" rowspan="2">Model</td><td rowspan="2">depth field</td><td rowspan="2">color field</td><td rowspan="2">Overall size</td><td colspan="3">Compression ratio</td>

<td>Depth</td><td>Colour</td><td>Total</td>

<td rowspan="2">"Morton256"</td><td>Original</td><td> 172.758</td><td> 321.666</td><td> 494.424</td><td rowspan="2"> 5,4</td><td rowspan="2"> 1,2</td><td rowspan="2"> 1,63</td>

<td>Compressed</td><td> 31.979</td><td> 270.597</td><td> 302.576</td>

<td rowspan="2">"Angel"</td><td>Original</td><td> 166.372</td><td> 302.508</td><td> 468.880</td><td rowspan="2"> 5,2</td><td rowspan="2"> 1,2</td><td rowspan="2"> 1,6</td>

<td>Compressed</td><td> 32.047</td><td> 262.209</td><td> 294.256</td>

Table 5. Lossless Geometry and Lossy Color Compression for the Lower Resolution PointTexture (In Bytes).

<td colspan="2" rowspan="2">Model</td><td rowspan="2">depth field</td><td rowspan="2">color field</td><td rowspan="2">Overall size</td><td colspan="3">Compression ratio</td>

<td>Depth</td><td>Colour</td><td>Total</td>

<td rowspan="2">"Morton256"</td><td>Original</td><td> 172.758</td><td> 321.666</td><td> 494.424</td><td rowspan="2"> 5,4</td><td rowspan="2"> 8,0</td><td rowspan="2"> 6,8</td>

<td>Compressed</td><td> 31.979</td><td> 40.352</td><td> 72.331</td>

<td rowspan="2">"Angel"</td><td>Original</td><td> 166.372</td><td> 302.508</td><td> 468.880</td><td rowspan="2"> 5,2</td><td rowspan="2"> 7,9</td><td rowspan="2"> 6,7</td>

<td>Compressed</td><td> 32.047</td><td> 38.408</td><td> 70.455</td>

3.2. Image Compression Octree

Table 6 presents the compressed and uncompressed component sizes of octree for our two test models. We see that the reduction of this field is around between 1.6 and 1.9 times.

However, compared to the uncompressed DotTexture models, even with the 10 8-bit depth field, OctreeImage is much more compact. Table 7 shows the compression ratios 7.2 and 11.2. This is more than PointTexture can be compressed without becoming OctreeImage (6.7 and 6.8 times, respectively).

However, as we have already mentioned, OctreeImage may contain incomplete color information, which is the case in the 'Angel' model. In such cases, three-dimensional color interpolation is used.

To summarize, we can conclude that the experiments presented above demonstrate the effectiveness of the 15 compression tools developed. The selection of the best tool for a given model depends on its geometric complexity, the character of the color distribution, the required rendering speed, and other factors.

Table 6. Compression ratios obtained by the procedure described in 4.1.2, for OctreeImage models and its components (file sizes rounded to Koctets).

<td>Model</td><td>Octtree Size</td><td>Octtree compressed size</td><td>Compression ratio</td>

<td>"Angel"</td><td> 50</td><td> 31</td><td> 1.6</td>

<td>"Morton256"</td><td> 41</td><td> 22</td><td> 1,9</td>

ES 2 374 064 T3

Table 7. Uncompressed PointTexture (8-bit depth field) and compressed OctreeImage representations for the same models (file sizes rounded to Koctets).

<td>Model</td><td>PointTexture</td><td>Compressed Octree Image</td><td>Compression ratio</td>

<td>"Angel"</td><td> 469</td><td> 65</td><td> 7.2</td>

<td>"Morton256"</td><td> 494</td><td> 44</td><td> 11,2</td>

5. Observations on the study of ISO / IEC 14496-1 / PDAM4

After applying the following revisions to the ISO / IEC 14496-1 / PDAM4 Study (N4627), the revised ISO / IEC 14496-1 / PDAM4 Study should be incorporated into ISO / IEC 14496-1 / FPDAM4.

Clause 6.5.3.1.1, Technique

Problem: The default value for the spelling field should be the most commonly used value.

Solution: Replace the default value of the spelling field "FALSE" with "TRUE", as follows.

Proposed revision:

spelling SFBool field TRUE

Clause 6.5.3.1.1, Technique

Problem: DIBR flow will be done with the uniform flow procedure for AFX.

Solution: Remove the URLImageWithDepth field from theImageWithDepth node.

Proposed revision:

ImageWith Depth {

<td>field</td><td>SFVec3f</td><td>position</td><td> 0 0 10</td>

<td>field</td><td>SFRotation</td><td>orientation</td><td> 0 0 1 0</td>

<td>field</td><td>SFVec2f</td><td>field of view</td><td> 0,785398 0,785398</td>

<td>field</td><td>SFFloat</td><td>Flat Close</td><td> 10</td>

<td>field</td><td>SFFloat</td><td>Far plane</td><td> 100</td>

<td>field</td><td>SFBool</td><td>orthographic</td><td>TRUE</td>

<td>field</td><td>SFNode</td><td>diTexture</td><td>NULL</td>

}

Clause 6.5.3.1.2, Editing

Problem: The term 'normalized' is misleading, as applied to depth field in the current context.

Solution: In the 5th paragraph, change 'normalized' to 'adjusted'.

Proposed revision:

The Near Plane and Far Plane fields specify the distances from the viewpoint to the near plane and the far plane of the visibility area. The texture and depth data shows the area enclosed by the near plane, the far plane, and the field of view. The depth data is adjusted to the distance between the Near Plane and the Far Plane.

Clause 6.5.3.1.2, Technique

Problem: DIBR flow will be done with the uniform flow procedure for AFX.

Solution: Remove the explanation from the URLImagenWithDepth field (the 7th paragraph and following).

ES 2 374 064 T3

Proposed revision:

Clause 6.5.3.2.2, Editing

Problem: The semantics of the depth field are incompletely specified.

Solution: Change the depth field specification in the 3rd paragraph as follows.

Proposed revision:

The depth field specifies the depth for each pixel in the texture field. The size of the depth map will be the same size as the image or movie in the texture field. The depth field will be one of several types of texture nodes (DelmagenTexture, FilmTexture, or PixelTexture), where only nodes that represent grayscale images are allowed. If the depth field is not specified, the alpha channel in the texture field will be used as the depth map. If the depth map is not specified via the depth field or alpha channel, the result is undefined.

The depth field allows us to calculate the effective distance of the three-dimensional points of the model to the plane that the point of view passes through, and is parallel to the near plane and the far plane:

<td>dist = Near Plane +</td><td>d - 1 (PlanoLeiano - PlanoCercano), -1</td>

where d is the depth value and dmax is the maximum allowable depth value. It is assumed that, for the points of the model, d> 0, where d = 1 corresponds to the far plane and d = dmax corresponds to the near plane.

This formula is valid for both perspective and orthographic cases, since d is the distance between the point and the plane. dmax is the largest value of d that can be represented by the bits used for each pixel:

(1) If the depth is specified by the depth field, then the depth d value equals the grayscale.

(2) If the depth is specified by the alpha channel in the image defined by the texture field, then the depth value is equal to the value of the alpha channel.

The depth value is also used to indicate which points belong to the model: only the point for which d is non-zero belongs to the model.

For the animated model based on DepthPicture, only DepthPicture is used with SimpleTexture as diTexture.

Each of the Simple Textures can be animated in one of the following ways:

(1) the depth field is a still image that satisfies the above condition, and the texture field is an arbitrary FilmTexture (2) the depth field is an arbitrary FilmTexture that satisfies the above condition about the depth field, and the texture field is a still image (3) both depth and texture are FilmTexture, and depth field satisfies the above condition (4) depth field is not used, and the depth information is retrieved from the FilmTexture alpha channel animating the texture field

Clause 6.5.3.3.2, Editing

Problem: The semantics of the depth field are incompletely specified.

Solution: Replace the depth field specification (3rd paragraph) with the proposed revision.

Proposed revision:

The geometric meaning of depth values, and all the conventions on their interpretation, adopted for SimpleTexture, apply here as well.

The depth field specifies multiple depths of each point on the projection plane, which is assumed to be the Far Plane (see above) in the pan order, starting at the point in the lower left corner and

ES 2 374 064 T3 moves to the right to finish the horizontal line, before moving to the top line. For each point, the number of depths (pixels) is stored first, followed by that number of depth values.

Clause 6.5.3.4.1, H.1, Technique

Problem: SFString field type, used for octree field, could lead to inconsistent values

Solution: Change field type for octree field to MFInt32

Proposed revision:

In clause 6.5.3.4.1 MFInt32 octree field

In clause H.1, table for Octree, change the column of the octree as follows:

<td colspan="2">Field Name</td><td>DEF identifier</td><td>Entry Identifier</td><td>OUTPUT identifier</td><td>DYN identifier</td><td>[m, M]</td><td>Q</td><td>TO</td>

<td>octree</td><td>I MFInt32</td><td> 01</td><td></td><td></td><td></td><td> [0,255]</td><td> 13,8</td><td></td>

Clause 6.5.3.4.1, Technique

Problem: DIBR flow will be done with the uniform flow procedure for AFX.

Solution: Remove the URLOcttree field from the OctreeImage node.

Proposed revision:

ImagenOctárbol {

<td>field</td><td>SFInt32</td><td>resolution octree</td><td> 256</td>

<td>field</td><td>MFInt32</td><td>octree</td><td> “”</td>

<td>field</td><td>MFNode</td><td>images october</td><td> []</td>

}

Clause 6.5.3.4.2, Editing

Problem: the definition of the octreeresolution field (2nd paragraph) admits errors of interpretation.

Solution: Check the description by adding the word 'admissible'

Proposed revision:

The octree resolution field specifies the maximum allowable number of leaves of the octree along one side of the surrounding cube.

The octree level can be determined from octreeresolution, using the following equation: octreelevel = int (log2 (octreeresolve-1)) + 1)

Clause 6.5.3.4.2, Technique

Problem: The DIBR flow will be done with the uniform flow procedure for AFX,

Solution: Remove the explanation from the URLOctárbol field (the 5th paragraph and following).

Proposed revision:

Clause 6.5.3.4.2, Editing

Problem: The animation of OctreeImage was incompletely described.

Solution: Add a paragraph at the end of clause 6.5.3.4.2 that describes the animation of ImageOcttree

ES 2 374 064 T3

Proposed revision:

Animation of OctreeImage can be carried out using the same approach as in the first three forms of DepthImage-based animation, described above, with the only difference being the use of the Octree field instead of the depth field.

Clause H.1, Technical

Problem: The depth data range in the PointTexture node may be too small for future applications. Many graphical tools support 24-bit or 36-bit depth for their z buffer. However, the depth field in PointTexture has the range of [0, 65,535], which is 16 bits.

Solution: In clause H.1, table for PointTexture, change the depth column range as proposed.

Proposed revision:

<td colspan="2">Field Name</td><td>DEF identifier</td><td>Entry Identifier</td><td>OUTPUT identifier</td><td>DYN identifier</td><td>[m, M]</td><td>Q</td><td>TO</td>

<td>Depth</td><td>I MFInt32</td><td> 10</td><td></td><td></td><td></td><td>[0, I]</td><td></td><td></td>

IV. ISO / IEC JTC 1 / SC 29 / WG 11 - FILM AND AUDIO CODING

1. Introduction

In this document, an enhancement of Octree Image in Depth Image Based Rendering (DIBR), AFX A8.3, is described. The OctreeImage node has been accepted and included in a proposal for Committee Draft during the meeting in Pattaya, PDAM of ISO / IEC 14496-1 / AMD4, “Org. International for Standardization, N4415, December 2001, pages 1-287 (XP001089813). However, it has been observed that the rendering quality would be unsatisfactory in some special cases, due to the occlusion of the object geometry. This document describes the improved version of the Octree Image node, that is, the Binary Volumetric Octree with Texture (TBVO), as well as its compression procedure for sending streams.

2. Textured Binary Volumetric Octree (TBVO)

2.1. TBVO overview

The goal of TBVO is to devise a more flexible rendering / compression format, with fast visualization, as an enhancement to the Binary Volumetric Octree (BVO). This is accomplished by storing some additional information based on the BVO. The BVO-based rendering consists of (octree structure + reference image set), while the TBVO-based rendering consists of (BVO octree structure + reference image set + camera indices).

The main problem in displaying the BVO is that we must determine the corresponding camera index of each voxel during rendering. To this end, we need not only to project to the cameras, but also to carry out the reverse beam diffusion procedure. At least, we must determine the existence of a camera, from which the voxel is visible. Therefore, we must find all the voxels that are projected towards a specific camera. But this procedure is very slow if we use the brute force approach. We have developed an algorithm that does this quickly and accurately for most object shapes. However, there are still some issues for voxels that are not visible from any camera.

A possible solution could be to store the explicit color for each voxel. However, in this case, we have experienced some problem compressing color information. That is, if we group voxel colors as an image format and compress it, the color mapping of neighboring voxels is destroyed, such that the compression ratio is unsatisfactory.

In TBVO, the problem is solved by storing the camera (image) index for each voxel. The index is usually the same for large groups of voxels, and this allows the use of an octree structure for economical storage of additional information. Note that, on average, only a 15% volume increase was observed in the experiments with our models. Its modeling is a bit more complex, but it supports a more flexible way of representing objects of any geometry.

The advantages of TBVO over BVO are that its representation is simpler and much faster than that of BVO, and

ES 2 374 064 T3 that virtually no restriction is imposed on the geometry of the object.

2.2. TBVO example

In this section we show a typical example, illustrating the efficacy and key ingredients of the TBVO rendering. In FIG. 12 (a), a BVO model of the “Angel” is shown. Using the usual 6 BVO textures, a few parts of the body and wing are not seen from any camera, producing a rendered image with lots of visible 'cracks'. In the representation of the TBVO of the same model, a total of 8 cameras are used (6 faces of a box + 2 additional cameras). In FIG. 13, (a) is the camera index image. The different color indicates the different index of the camera. Additional cameras are located inside the cube, observing the front and rear face orthographically. In FIG. 13, (b) and (c) are additional images taken by the additional cameras. As a result, we have obtained a clear and seamless rendering result of the model, as shown in FIG. 12 (b).

2.3. Description of the uncompressed flow of the TBVO

We assume that 255 cameras are sufficient, and we allocate up to 1 octet for the index. The TBVO stream is a stream of symbols. Each TBVO symbol is either a BVO symbol or a Texture symbol. The Texture symbol indicates a camera index, which could be a specific number or an "undefined" code. Be '?' the "undefined" code for further description.

The TBVO flow is traversed in amplitude order first. Let's describe how to record the TBVO stream if we have a BVO and each terminal node voxel has camera number. This must be done at the modeling stage. It will loop through all the nodes of the BVO, include the terminal nodes (which have no BVO symbol) in amplitude order first. The following pseudo-code will complete the recording of the stream.

If NodoAct is not terminal node {Record current BVO-symbol corresponding to this node if all children have identical camera index (texture-symbol)

If NodoAct's parent has camera index '?'

Record equal camera index for subnodes} otherwise {Record '?' Symbol }

According to the procedure, for the TBVO tree shown in FIG. 14 (a), a stream of symbols can be obtained as shown in FIG. 14 (b). In this example, the texture symbols are represented in octets. However, in cash flow, each texture symbol would only need 2 bits, because we only need to represent three values (two cameras and the undefined code).

2.4. TBVO compression

The octree image and octree fields, in the Octree Image node, are compressed separately. The procedures described have been developed based on the concept that the octree field must be compressed without loss, while some degree of visually acceptable distortion is allowed for octree images.

2.4.1. Compression of the octree image field

The octree image field is compressed by means of MPEG-4 image compression (for the static model), or video compression tools (for the animated model) that are allowed in the MPEG-4 standard. In our approach, we use the JPEG format for Octree Images (after some preprocessing we call 'minimization' of the JPEG images, retaining for each texture only the dots necessary for three-dimensional display; in other words, the parts of the given texture that are never used in the 3D rendering stage can be compressed as grossly as we like).

2.4.2. Octtree field compression

Octree compression is the most important part of OctreeImage compression, as it deals with compressing an already very compact representation of a binary tree with no links. However, in our experiments, the procedure explained below reduced the volume of this structure by about half.

ES 2 374 064 T3 of the original. In the animated version of OctreeImage, the octree field is compressed separately for each three-dimensional frame.

2.4.2.1 Context model

Compression is carried out by a variant of adaptive arithmetic coding (implemented as a 'distance coder') that makes explicit use of the geometric nature of the data. The Octree is a stream of bytes. Each octet represents a node (that is, a subcube) of the tree, in which its bits indicate the occupation of the subcube after the internal subdivision. The bit pattern is called the node fill pattern. The described compression algorithm processes the bytes one by one, as follows.

* A context is determined for the current octet.

* The 'probability' (normalized frequency) of occurrence of the current octet in this context is extracted from the 'probability table' (PT) corresponding to the context.

* The probability value is supplied to the distance encoder.

* The current PT is updated by adding 1 to the frequency of occurrence of the current octet in the current context (and, if necessary, renormalized later, see details below).

Therefore, coding is the process of building and updating PTs according to the context model. In context-based adaptive arithmetic coding schemes (such as 'Partial Match Prediction'), the context of a symbol is usually a string of several preceding symbols. However, in our case, the efficiency of compression is increased by exploiting the structure of the octree and the geometric nature of the data. The approach described is based on the two ideas that are apparently new to the octree compression problem.

A. For the current node, the context is either its parent node, or the pair {parent node, current position of node at parent node};

B. The 'probability' of the occurrence of the given node at the specific geometric location at the specific parent node is assumed to be invariant with respect to a certain set of orthogonal transforms (such as rotations or symmetries).

Hypothesis 'B' is illustrated in FIG. 6, for the transform R, which is the rotation by -90 ° in the xz plane. The basic notion behind 'B' is the observation that the probability of occurrence of a specific type of child node at a specific type of parent node should depend only on its relative position. This hypothesis is confirmed in our experiments, by the analysis of the probability tables. It allows us to use a more complex context without having too many probability tables. This, in turn, helps achieve pretty good results in terms of data size and speed. Note that the more contexts that are used, the more accurate the estimated probability and, therefore, the more compact the code.

Let us introduce the set of transforms for which we will assume the invariance of the probability distributions. In order to apply to our situation, such transforms should preserve the surrounding cube. Let us consider a set G of the orthogonal transforms in the Euclidean space, which are obtained by all the compositions, in any number and order, of the 3 basic transforms (generators) m · ,, m2 and m3, given by

where m-ι ym2 are reflections on the planes x = y and y = z, respectively, and m3 is the reflection on the plane x = 0. One of the classic results of the theory of groups generated by reflections states that G contains 48 different orthogonal transforms and is, in a sense, the maximum group of orthogonal transforms that take the cube to itself himself (the so-called Coxeter group). For example, the rotation R in FIG. 6 is expressed, by means of generators, as

R = m3 m2 πη m2, where '·' is matrix multiplication.

The transform from G, applied to an octree node, produces a node with a different pattern of subcube filling. This allows us to categorize the nodes according to the fill pattern of their subcubes. Using the language of

ES 2 374 064 T3 group theory [5], we say that G acts on the set of all the filling patterns of the octree nodes. Calculations show that there are 22 distinct classes (also called orbits in group theory), in which, by definition, two nodes belong to the same class if, and only if, they are connected by a transform from G. The number of Elements in a class ranges from 1 to 24, and is always a divisor of 48.

The practical consequence of hypothesis 'B' is that the probability table depends not on the parent node itself, but only on the class to which the parent node belongs. Note that there would be 256 tables for a parent-based context and 256x8 = 2048 additional tables for the parent-child position-based context in the above case, while we only need 22 tables for the parent class-based context, plus 22x8 = 176 tables in the last case. Therefore, it is possible to use an equivalently complex context with a relatively small number of probability tables. The constructed PT would have the form shown in Table 8.

Table 8. Enumeration of probability tables.

<td>PT identifier</td><td> 0</td><td> 1</td><td></td><td> 255</td><td>Context description</td>

<td> 0</td><td>P0.0</td><td>P0.1</td><td></td><td>P0.255</td><td>Context-0: independent of context</td>

<td> 1..22 (22)</td><td>Pi, 0</td><td>Pi, 1</td><td></td><td>Pi, 255</td><td>Context-1: {parent node class}</td>

<td> 23...198 (176)</td><td>Pj, 0</td><td>Pj, 1</td><td></td><td>Pj, 255</td><td>Context-2: {parent node class, current node position}</td>

2.4.2.2. Encoding process

To make the statistics for the probability tables more accurate, they are collected in different ways in three stages of the coding process.

* In the first stage we do not use contexts at all, accepting the 'context-0 model', and we maintain a single probability table with 256 entries, from the uniform distribution;

* As soon as the first 512 nodes (it is an empirically found number) are hard-coded, we switch to 'context model-1', using the parent node as a context. At the time of switching, the PT of context-0 is copied to PTs for all 22 contexts.

* After the next 2048 nodes (another heuristic value) are hard-coded, we switch to 'context model2'. At this time, the context-1 PTs of the parent patterns are copied to the PTs for each position in the same parent pattern.

The key point of the algorithm is the determination of the context and the probability for the current octet. This is implemented as follows. In each class we set a single element, which is called the 'standard element'. We store a class map table (CMT) that indicates the class to which each of the possible 256 nodes belongs, and the precomputed transform of G that takes this specific node to the standard element of its class. Thus, in order to determine the probability of the current node N, we carry out the following steps:

* Look at the parent P of the current node;

* Extract the class from the CMT to which P belongs, and the transform T that takes P to the standard node of the class. Let c be the class number;

* Apply T to P, and find the position p of the child in the standard node to which the current node N is associated;

* Apply T to N. Then, the newly obtained fill pattern TN is at position p at the standard node of class c.

* Extract the required probability from the TN entry of the probability table corresponding to the combination of class and position (c, p).

For the context-1 model, the previous stages are modified in an obvious way. It goes without saying that all transformations are precomputed, and implemented in a lookup table.

Note that in the decoding stage of node N, its parent P is already decoded and, therefore, the transform T is known. All the stages in the decoding phase are absolutely similar to the corresponding encoding stages.

ES 2 374 064 T3

Finally, let's outline the probabilities update process. Let P be a table of probabilities for some context. Let P (N) be the entry of P corresponding to the probability of occurrence of node N in this context. In our implementation, P (N) is an integer, and after each occurrence of N, P (N) updates as:

P (N) = P (N) + A, where A is an integer incremental parameter that usually ranges from 1 to 4 for different context models. Let S (P) be the sum of all the inputs in P: Then the 'probability' of N supplied to the arithmetic encoder (distance encoder in our case) is calculated as P / (N) / S (P). As soon as S (P) reaches a threshold value 216, all the inputs are renormalized: in order to avoid the occurrence of null values in P, the inputs equal to 1 are left intact, while the others are divided by 2.

2.4.2.3 Coding of 'camera nodes'

The stream of symbols that determine the texture (chamber) numbers for each voxel is compressed using its own probability table. In the terms used above, it has a single context. The PT entries are updated at a greater increment than the entries for the octree nodes; in the rest, there is no difference with the encoding of node symbols.

2.5. Results of the compression and representation of TBVO

FIGs. 15, 17, 18 and 19 are the results of the TBVO compression. In FIG. 16, the stripped images of the “Angel” and “Morton” models are illustrated. The compressed size is compared to the compressed BVO: in the third column, the number in brackets is the compressed geometry volume, while the first number is the total volume of the compressed model based on TBVO (that is, the textures). As a measure of visual distortion, PSNR (Signal to Image Noise Ratio) was calculated to estimate the color difference after the LDI-> 7 (T) BVO-> LDI transform. The size of the compressed model is the size of all textures (stored as minimized JPEGs, see 0), plus the size of the compressed geometry. In the case of TBVO, the compressed geometry also includes the camera information. The PSNR of the TBVO is significantly improved compared to the BVO.

The TBVO achieves a faster rendering than the BVO. For the "Angel" model, the frame rate of TBVO-12 is 10.8 frames per second, while that of BVO is 7.5. For the “Morton” model, that of TBVO-12 is 3.0 frames per second, while that of BVO is 2.1 (on a Celeron at 850 MHz). On the other hand, it is observed that the representation is much more accelerated in the animated TBVO. For the “Dragon” model, the TBVO-12 frame rate is 73 frames per second, while that of BVO is 29 frames per second (on a 1.8 GHz Pentium IV).

A TBVO format provides great flexibility. For example, 2 ways of using 12 cameras are illustrated in FIG. 6: TBVO12 and TBVO- (6 + 6). TBVO-12 uses 6 BVO cameras (cube faces) plus 6 images taken from the center of the cube, and parallel to the faces. The configuration (6 + 6) uses 6 BVO cameras, and then removes ('peels') all voxels visible by these cameras and 'photographs' the parts that became visible by the same 6 cameras. Examples of such images are shown in FIG. 16.

Note the drastic difference in quality (subjective, and the PSNR value) between the BVO and TBVO-6 Angel models. Although the same camera locations are used, TBVO allows us to assign camera numbers to all voxels, even those invisible to all cameras. These numbers are chosen in order to optimally match the original colors (ie for each point the best color match is selected in all 'camera images', regardless of line visibility. In the case of the Angel it gives a great Outcome).

Note also the very modest 'geometry' volume difference (ie, BVO + chambers) between chamber cases 6 and 12. In fact, the additional cameras usually cover small regions and therefore their identifiers are rare, and their textures are sparse (and well compressed). All of this applies not only to 'Angel', but also to 'Morton', 'Palmera512' and 'robots512'.

2.6. Node specification

ImagenOctárbol {

<td>field</td><td>SFInt32</td><td>resolution octree 256</td><td></td>

<td>field</td><td>MFInt32</td><td>octree</td><td>[] #% q = 13.8</td>

<td>field</td><td>MFInt32</td><td>Camera Identifier</td><td>[] #% q = 13.8</td>

<td>field</td><td>MFNode</td><td>images october</td><td> []</td>

ES 2 374 064 T3}

The OctreeImage node defines a TBVO structure, in which there is an octree structure, the corresponding array of camera indices and a set of Octreeimages.

The octreeimages field specifies a set of DepthImage nodes with SimpleTexture for the diTexture field; the depth field is not used in these SimpleTexture nodes. The spelling field must be TRUE for DepthImage nodes. For each of the Simple Textures, the texture field stores the color information of the object, or part of the object's view (for example, its cross-section through a camera plane) as obtained by the orthographic camera whose position and orientation are determined. specified in the corresponding DepthImage fields. Parts of the object, corresponding to each camera, are assigned at the model construction stage. The partition of the object, using the values of the position, orientation and texture fields, is carried out in order to minimize the number of cameras (or, equivalently, of the octree images involved), to include at once all the parts of the object potentially visible from an arbitrary chosen position. The orientation fields must satisfy the condition: the camera view vector has only one non-zero component (that is, it is perpendicular to one of the faces of the surrounding cube). Also, the sides of the SimpleTexture image must be parallel to the corresponding sides of the surrounding cube.

The octree field completely describes the geometry of the object. The geometry is represented as a set of voxels, which constitutes the given object. An octree is a wooded data structure, in which each node is represented by one octet. A 1 in the i-th bit of this octet means that child nodes exist for the i-th child of that inner node; while a 0 means that they do not exist. The order of an internal node is shown in FIG. 14 (b). The size of the surrounding cube of the total octree is 1x1x1, and the center of the cube of the octree will be the origin (0, 0, 0) of the local coordinate system.

The CameraIdentifier field contains an array of camera indices assigned to the voxels. In the rendering stage, the color attributed to a terminal leaf of the octree is determined by orthographically projecting the leaf onto one of the octree images, with a specific index. The indices are stored in the form of an octree: if a specific camera can be used for all leaves contained in a specific node, the node that contains the index of the camera is cast to the stream; otherwise, the node containing a fixed 'further subdivision' code is issued, which means that the camera index will be specified separately for the child subnodes of the current node (in the same recursive way). If the CameraIdentifier is empty, then the camera indices are determined during the rendering stage (as in the case of BVO).

The octreeresolution field specifies the maximum allowable number of terminal leaves of the octree along one side of the surrounding cube. The level of the octree can be determined from octree resolution, using the following equation:

treelevel = Γ log2

2.7. Bit stream specification

2.7.1. Octree compression

2.7.1.1. General view

The OctreeImage node in Depth Image Based Rendering defines the structure of the octree and its projected textures. Each texture, stored in the Octree Imaging array, is defined through the DepthImage node with SimpleTexture. The other fields of the OctreeImage node can be compressed by octree compression.

2.7.1.2. Octree

2.7.1.2.1. Syntax class Octtree ()

HeaderOcttree ();

aligned bit (32) * next;

while (next == 0x000001C8) {

aligned bit (32) octree_frame_start_code;

ES 2 374 064 T3

Octreeframe (Octreelevel) aligned bit (32) * next;

} }

2.7.1.2.2. Semantics

The compressed octree stream contains an octree header and one or more octree frames, each preceded by the octree_frame_start_code. The octree_frame_start_code value is always 0x000001C8. This value is detected by the forward parsing (next) of the stream.

2.7.1.3. HeaderOcttree

2.7.1.3.1. Syntax class OctreederHead () {unsigned int (5) OctreeResolution Bits;

unsigned int (BitsResolutionOcttree) ResolutionOcttree;

int tree level = ceil (log (OctResolution) / log (2));

unsigned int (3) NumBitsTexture;

unsigned int (NumBitsTexture) NumOfTextures;

}

2.7.1.3.2. Semantics

This class reads the header information for compression from the octree.

The Octree Resolution, whose length is described by Bits Octree Resolution, contains the value of the Octree Resolution field of the OctreeImage node. This value is used to get the level of the octree.

The NumOfTextures, which is NumBitsTexture long, describes the number of textures (or cameras) used in the OctreeImage node. This value is used for the arithmetic encoding of the Camera Identifier for each node in the octree. If the value of NumBitsTexture is 0, then the texture symbols are not encoded, setting the value of TextureAct of the root node to 255.

2.7.1.4. PlotOcttree

2.7.1.4.1. Syntax class OctreekFrame (int OctLevel) for (int ActLevel = 0; ActLevel <OctLevel; ActLevel ++ 0 for (int NodeIndex = 0; NodeIndex <nNodesInActLevel; NodeIndex ++){ int NodeSym = ArithmeticDecoderSymbol (ContextIdentifier);

if (TextureAct == 0) {

TextureAct = ArithmeticDecoderSymbol (IdentifierContextTexture);

} for (int NodeIndex = 0; NodeIndex <nNodosEnLivelAct; NodeIndex ++) if (TextureAct == 0)

ES 2 374 064 T3

TextureAct = ArithmeticDecoderSymbol (IdentifierContextTexture);

{

2.7.1.4.2. Semantics

This class reads a single octree frame in amplitude traversal order first. Starting from the 1st node at level 0, after reading each node at the current level, the number of nodes at the next level is known by counting all 1s in each node symbol. At the next level, that number of nodes (nNodosEnNivelAct) from the flow will be read.

For the decoding of each node, a suitable ContextIdentifier is given, as described in clause 2.7.1.6.

If the Texture (or Camera) Identifier for the current node (TextureAct) is not defined by the parent node, then the Texture Identifier is also read from the stream, using the context for the Texture Identifier, defined by TextContextIdentifier. If a non-null value is extracted (the Texture Identifier is defined), then this value will also apply to all child nodes at the next levels. After decoding each node, the TextureIdentifier will be assigned to the terminal leaf nodes of the octree that have not yet been assigned the TextureIdentifier value.

2.7.1.5. Adaptive Arithmetic Decoding

This section describes the adaptive arithmetic encoder used in octree compression, using the C ++ style syntactic description. decoder_aa () is the function that decodes a symbol, using a pattern specified by the entire array frec_acumul [] and PCT is a pattern of probability context tables, as described in clause 2.7.1.6.

int ArithmeticDecoderSymbol (int ContextIdentifier) unsigned int MAXCUM = 1 << 13;

unsigned int MAXCUMTexture = 256;

int * p, allim, maxcum;

if (IdentifierContext! = IdentifierContextTextura) p = PCT [IdentifierContext];

allim = 256;

maxcum = MAXCUM;

else p = PCTTexture;

allim = numOfTextures;

maxcum = MAXCUMTexture; } int frec_acumul [allim];

int cum = 0;

for (int i = allim-1; i> = 0; i--) {cum + = p [i];

frec_acumul [i] = cum;

if (cum> maxcum) {cum = 0;

for (int i = allim-1; i> = 0; i-) {PCT [Context Identifier] [i] = (PCT [Context Identifier] [i] +1) 2;

cum + = PCT [ContextIdentifier] [i];

ES 2 374 064 T3

FreqAcumul [i] = cum; } return decoder_aa (freq_accumul);

{

2.7.1.6. Decoding process

The general structure of the decoding process is described in clause 0 (see also the previous description of the encoding process). It shows how the TBVO nodes are obtained from the bit stream that make up the arithmetically coded (compressed) TBVO model.

At each stage of the decoding process we must update the context number (that is, the index of the probability table that we use), and the probability table itself. We call the Probabilistic model the union of all probability tables (integer formations). The j-th element of the ith probability table, divided by the sum of its elements, estimates the probability of occurrence of the j-th symbol in the ith context.

The process of updating the probability table is as follows. Initially, the probability tables are initialized such that all entries are equal to 1. Before decoding a symbol, the context number (ContextIdentifier) must be chosen. The ContextIdentifier is determined from previously decoded data, as indicated by 0 and 0 below. When the ContextIdentifier is obtained, the symbol is decoded using the binary arithmetic decoder. After that, the probability table is updated, adding an adaptation step to the frequency of the decoded symbol. If the total (cumulative) sum of table elements becomes greater than the cumulative threshold, then normalization is performed (see 2.7.1.5.1).

2.7.1.6.1. Modeling the context of the texture symbol

The texture symbol is modeled with only one context. This means that only one probability table is used. The size of this table is equal to the number of Textures plus one. Initially, this table is initialized with values all equal to 1. The maximum allowable input value is set to 256. The adaptive stage is set to 32. This combination of parametric values allows adaptation to a highly variable flow of numbers texture.

2.7.1.6.2. Modeling the context of the node symbol

There are 256 distinct node symbols, each symbol representing a binary array of voxels of dimensions 2x2x2. A three-dimensional orthogonal transformation can be applied to these formations, transforming the corresponding symbols into each other.

Let us consider a set of 48 fixed orthogonal transforms, that is, rotations in 90 * n (n = 0,1,2,3) degrees around the coordinate axes, and symmetries. Their matrices are given below, in the order of their numbers:

ES 2 374 064 T3

Orthogonal Transforms [48] = {

f 0 0 p O 01 (-1 O01

0 - '0 1 0 0 0-1 (oio (o O -1) (O 10) f ° 0 '1 f °0 -qf ° 1

I oh 0 O -10 0

V oo) (oio) (o O lj

O 0 11 O -11 gp

0 0 0 -1 0 0-1

O -1 oj (1 oo) (oo fo 1 01 p> I 01 Λ »-1

OO -1 1 0 0 00, 1 o oj (OO -lj V o il foo il (00-1-

O 0 10 -100 oj (-1 o oj (o 1°.

(IO 01 (-1 O 0 '

O 0 0 10-10

1J (O -1 oj (or O 1.

(-1 or 01 ro or -11

-1 O 01 10o

0) (or -1 oj (or -Ioj

OO Γ -10 0

O -1 o, (Ο o -Ιο -I o (-1 oo (oo Γ 0-10 k-1 0 Q

Ό or -1 '

O 1 o

-1 OO fo 0 -> 1 f ° o]

-10 OO Oll (or -1 oj (-1 OOj

-1 OR 0 '

0-10

OO -I (O -1 0 '0 0-1 ll O

O -1 01 oo (o O -lj 'O -1 0' -10 0 .0 0 ->, l O 01 OO -1 P - ° J

Ό i ol

OO -1 -1 0

O 0 '0-10 0 O -1,

Ό i 0 '-10 0 A 0 (-1 OR 0 '

0-1

Or -1 or,

-1 or ol

O 1 o .0 O -lj

There are 22 sets of symbols - called classes -, so that 2 symbols are connected by such a transform if and only if they belong to the same class. The encoding procedure constructs the PCTs as follows: the ContextIdentifier of a symbol is equal to either the class number to which its parent belongs, or a combined number (parent class, current node position in node dad). This allows for a large reduction in the number of 10 contexts, reducing the time required to obtain meaningful statistics.

For each class, a single base symbol is determined (see Table II and, for each symbol, the orthogonal transform that takes it to the base symbol of its class is precalculated (in the actual encoding / decoding process, the table of lookup.) After the ContextIdentifier is determined for a symbol, the transform, inverse (that is, matrix transposed) of the one that takes its parent to the base element, is applied. In Table 9, the 15 contexts and the corresponding direct transforms are given for each symbol.

Table 9. Example of base symbol for each class

<td>Class</td><td>Base symbol example</td><td>Class order (Number of elements)</td>

ES 2 374 064 T3

The context model depends on the number N of symbols already decoded:

For N <512 there is only one context. The probability table is initialized with all 1 values. The number of symbols in the probability table is 256. The adaptation stage is 2. The maximum cumulative frequency is 8,192.

For 512 <N <2,560 (= 2,048 + 512), the context-1 model is used (in the sense that the context number is a single parameter, the class number). This model uses 22 pct. The ContextIdentifier is the number of the class to which the parent of the decoded node belongs. This number can always be determined from the lookup table (see Table III), because the parent is decoded before the child. Each of the 22 PCTs is initialized by the PCT from the previous stage. The number of symbols in each probability table is 256. The adaptation stage is 3. The maximum cumulative frequency is also 8,192. After the symbol is decoded, it is transformed using the inverse orthogonal transform defined above. The orthogonal transform number can be found in Table III, with the Node Symbol Identifier equal to the parent of the current node symbol.

When 2560 symbols are decoded, the decoder switches to context-2 (in the sense that the context number is now made up of the two parameters, as explained later). This model uses 176 (= 22 * 8, that is, 22 classes by 8 positions) PCT. The ContextIdentifier here depends on the class of the parent and the position of the current node in the parent node. The initial probability tables for this model depend only on its context, but not on the position: for all 8 positions, PCT is a clone of the PCT obtained for the class given in the previous stage. The number of symbols in each probability table is 256. The adaptation stage is 4. The maximum cumulative frequency is also 8,192.

After the symbol is decoded, it is also transformed using the inverse orthogonal transform (to the one given in Table III), as in the previous model.

The geometry of the base elements for each class can be easily obtained, using Table 10. The base elements are exactly the symbols for which the Transform Identifier is 0 (the number 0 is assigned to the identical transform).

ES 2 374 064 T3

Table 10. Joint lookup table for the node symbol, its class number, and the orthogonal transform that takes the symbol to the fixed base element of this class

<td>Node Symbol Identifier</td><td>Class Identifier</td><td>Identifier of Orthogonal transform</td><td>Node Symbol Identifier</td><td>Identifier Class</td><td>Identifier of Orthogonal transform</td><td>Node Symbol Identifier</td><td>Identifier Class</td><td>Orthogonal Transform Identifier</td>

ES 2 374 064 T3

ES 2 374 064 T3

Hereinafter, the MPEG-4 node specification and the compression techniques of the octree image formats used in the depth image-based three-dimensional rendering apparatus and method according to the present invention will be described in detail.

This invention describes a family of data structures, Depth Image Based Representations (DIBR), that provide effective and efficient representations, mostly based on depth images and maps, fully utilizing the advantages described above. Let us briefly characterize the main formats of DIBR: SimpleTexture, PointTexture and OctreeImage.

FIG. 20 is a diagram of an example of the texture image and depth map, and FIG. 21 is a diagram of an example Layered Depth Image (LDI). (a) shows the projection of the object and (b) shows the layered pixels.

SimpleTexture is a data structure consisting of an image, the corresponding depth map, and the description of the camera (its position, orientation and type, orthogonal or in perspective). The rendering capabilities of a single SimpleTexture are restricted to objects such as the façade of a building - a depth mapped frontal image, which allows reconstruction of views of the façade at a significant range of angles. However, the collection of Simple Textures produced by properly placed cameras allows the representation of the entire building - in case the reference images cover all potentially visible parts of the building surface. Of course, the same goes for trees, human figures, cars, etc. Also, joining SimpleTextures provides a fairly natural means of manipulating 3D animated data. In this case, the reference images are replaced by reference video streams. The depth maps for each three-dimensional frame can be represented either by alpha channel values of these video streams, or by separate gray-scale video streams. In this type of rendering, images can be stored in lossy compressed formats like, say, JPEG. This significantly reduces the volume of the color information, especially in the animated case. However, the geometry information (depth maps) should

ES 2 374 064 T3 be compressed without loss, which affects the overall reduction in storage.

For objects of complex shape, it is sometimes difficult to cover the entire visible surface with a reasonable number of reference images. The preferable representation for such cases might be PointTexture. This format also stores a reference image and a depth map, but in this case both are multivalued: for each line of sight provided by the camera (orthographic or perspective), the color and distance are stored for each intersection of the line with the object. The number of intersections can vary from line to line. Joining multiple PointTextures provides a highly detailed representation, even for complex objects. But the format largely lacks the two-dimensional regularity of SimpleTexture, and therefore has no natural image-based compressed shape. For the same reason, it is used only for fixed objects.

The OctreeImage format occupies an intermediate position between the 'mostly two-dimensional' SimpleTexture and the 'mostly three-dimensional' PointTexture: it stores the object's geometry in the volumetric representation structured as an octree (hierarchically organized voxels of the usual binary subdivision of the surrounding cube), while that the color component is represented by a set of images. This format also contains an additional octree-like data structure, which stores, for each terminal leaf voxel, the index of a reference image containing its color. In the Octree Image rendering stage, the color of the terminal leaf voxel is determined by orthographically projecting it onto the corresponding reference image. We have developed a very efficient compression procedure for the geometry part of the Octree Image. It is a variant of context-based adaptive arithmetic coding, where contexts are constructed with the explicit use of the geometric nature of the data. The use of compression, along with lossy compressed reference images, makes OctreeImage a very space-efficient representation. Like SimpleTexture, OctreeImage has an animated version: reference video streams instead of reference images, plus two additional octree streams representing the geometry and voxel-image correspondence for each three-dimensional frame. A very useful feature of an OctreeImage format is its implicit medium association capacity.

The DIBR family has been developed for the new version of the MPEG-4 standard, and adopted for inclusion in the MPEG Animation Environment Extension (AFX). AFX provides further enhanced features for synthetic MPEG-4 environments, and includes a collection of interoperable tools that produce a reusable architecture for interactive animated content (compatible with existing MPEG-4). Each AFX tool shows support for a BIFS node, a synthetic stream, and an audiovisual stream. The current version of AFX consists of higher-level descriptions of animation (eg, skin and bone based animation), enhanced rendering (eg, procedural texturing, light and field association), compact representations (eg NURBS, solid representation, subdivision surfaces), low bit rate animations (eg. g., interpolator compression) and others, as well as our proposed DIBR.

The DIBR formats were designed to combine the benefits of various ideas suggested above, providing a user with the flexible tools best suited for a specific task. For example, the non-animated SimpleTexture and PointTexture are specific cases of the known formats, while OctreeImage is a seemingly new representation. But in the context of the MPEG-4 standard, the three basic formats of DIBR can be considered as building blocks, and their combinations by means of MPEG-4 constructs not only encompass many of the image-based representations suggested in the bibliographies, but also they provide great potential for building such new formats.

Now Depth Image Based Rendering will be described.

Taking into account the ideas outlined in the previous section, as well as some of our own developments, we suggest the following set of image-based formats, for use in MPEG-4 AFX: SimpleTexture, PointTexture, DepthImage, and OctreeImage. Note that SimpleTexture and OctreeImage have animated versions.

SimpleTexture is a single image combined with an image with depth. It is equivalent to RT, while PointTexture is equivalent to LDI.

Based on SimpleTexture and DotTexture as foundations, we can build a wide variety of representations using MPEG-4 constructs. The formal specifications will be given later, and here we describe the result geometrically.

The DepthImage structure defines either a SimpleTexture or a PointTexture, along with the surrounding enclosure, position in space, and some other information. A set of DepthPictures can be unified under a single structure called a Transform node, and this allows the construction of a wide variety of useful representations. The most widely used are the two that do not have a specific MPEG-4 name, but in our practice we call them Enclosure Texture (BT) and Generalized Enclosure Texture (GBT). BT is a

ES 2 374 064 T3 union of six Simple Textures corresponding to a surrounding cube of an object or scene, while GBT is an arbitrary union of any number of Simple Textures, which together provide a coherent three-dimensional representation. An example of BT is given in FIG. 22, where reference images, depth maps and the resulting three-dimensional object are shown. BT can be represented with the help of an incremental distortion algorithm, but we use a different approach, applicable to GBT as well. An example of the GBT representation is shown in FIG. 23, where 21 SimpleTextures are used to represent a complex object, the palm tree.

It should be noted that the unifying mechanisms allow, for example, the use of several LDIs with different cameras, to represent the same object, or ports of the same object. Therefore, data structures such as image-based objects, cells in the LDI tree, cells in the surfels-based tree structure, are all particular cases of this format, which obviously offers much greater flexibility in the adaptation of the location and resolution of Simple Textures and Point Textures to the structure of the scene.

Next, the Octree Image: Textured Binary Volumetric Octree (TBVO) will be described.

In order to use multi-resolution texture and geometry with a more flexible rendering and fast rendering, we developed the OctreeImage rendering, which is based on the Textured Binary Volumetric Octree (TBVO). The goal of TBVO is to devise a flexible rendering / compression format with high quality fast display. The TBVO consists of three main components: the Binary Volumetric Octree (BVO), which represents the geometry, a set of reference images and image indices corresponding to the nodes of the octree.

Geometric information in the form of BVO is a set of regularly spaced (occupied or empty) binary voxels, combined into larger cells in the usual way of octrees. This representation can be easily obtained from DepthImage data, through the intermediate form of 'point cloud', since each pixel with depth defines a single point in three-dimensional space. Conversion of point cloud to BVO is illustrated in FIG. 24. An analogous process allows the conversion of the polygon model to BVO. The BVO texture information can be extracted from the reference images. A reference image is a texture of voxels at a given camera position and orientation. Therefore, the BVO itself, together with the reference images, already provides the representation of the model. However, it turned out that an additional structure, which stores the image index for each terminal sheet of the BVO, allows a much faster and better quality display.

The main problem in displaying the BVO is that we must determine the corresponding camera index of each voxel during rendering. To this end, we must at least determine the existence of a camera, from which the voxel is visible. This procedure is very slow if we use the brute force approach. In addition to this problem, there are still some difficulties for voxels that are not visible from any camera, causing undesirable distortions in the rendered image.

A possible solution could be to store the explicit color for each voxel.

However, in this case, we have experienced some problem compressing the color information. That is, if we group voxel colors as an image format and compress it, the color mapping of neighboring voxels is destroyed, so the compression ratio would be unsatisfactory.

In TBVO, the problem is solved by storing the camera (image) index for each voxel. The index is usually the same for large groups of voxels, and this allows the use of the octree structure for economical storage of additional information. Note that, on average, only a 15% volume increase was observed, compared to the representation using only BVO and reference images, in the experiments with our models. Its modeling is a bit more complex, but it supports a more flexible way of representing objects of any geometry.

Note that the TBVO is a very convenient representation to represent with the help of splats, because the size of the splat is easily calculated from the size of the voxel. Voxel color is easily determined using reference images and voxel image index

Now we will describe the sending of streams of the textured binary volumetric octree. We assume that 255 cameras are sufficient, and we allocate up to 1 octet for the index. The TBVO flow is a flow of symbols. Each TBVO symbol is either a BVO symbol or a Texture symbol. The Texture symbols indicate a camera index, which could be a specific number or an "undefined" code.

Be '?' the "undefined" code for further description. The BVO flow is traversed in amplitude order first. Now let's describe how to record the TBVO stream if we have the BVO and each terminal leaf voxel has image index. This must be done at the modeling stage. It will cycle through all the nodes in the BVO, including the terminal leaf nodes (which do not have a BVO symbol) in amplitude order first. In FIG. 25, the pseudo-code that completes the recording of the stream is displayed.

ES 2 374 064 T3

An example of TBVO bitstream recording is shown in FIG. 14. For the TBVO tree shown in FIG. 14 (a), a stream of symbols can be obtained as shown in FIG. 14 (c), according to the procedure. In this example, the texture symbols are represented in octets. However, in cash flow, each texture symbol would need 2 bits, because we only need to represent three values (two cameras and the undefined code).

The DIBR Animation will be described below.

Animated versions were defined for two of the DIBR formats: DepthImage, which contains only SimpleTextures, and OctreeImage. The volume of data is one of the crucial issues in 3D animation. We have chosen these specific formats because video streams can naturally be incorporated into animated versions, providing a significant reduction in data.

For ImageWith Depth, animation is performed by replacing the reference images with FilmTextures of the MPEG-4 standard. High-quality lossy video compression does not seriously affect the appearance of the resulting 3D objects. Depth maps can be stored (in almost lossless mode) in the alpha channels of the reference video streams. In the rendering stage, the three-dimensional frame is rendered after all the reference images and depth frames are received and decompressed.

The animation of OctreeImage is similar: the reference images are replaced by MPEG-4 standard MovieTexture, and a new stream of the Octree appears.

The MPEG-4 Node Specification will now be defined.

The DIBR formats are described in detail in the MPEG-4 AFX node specifications. The DepthImage contains fields that determine the parameters of the truncated pyramid in view, either for the SimpleTexture or for the PointTexture. The OctreeImage node represents the object in the form of a TBVO-defined geometry and a set of reference image formats. The information dependent on the scene is stored in special fields of the DIBR data structures, allowing the correct interaction of the DIBR objects with the rest of the scene. The definition of the DIBR nodes is shown in FIG. 26.

FIG. 27 illustrates the special layout of the DepthImage, which shows the meaning of each field. Note that the DepthImage node defines a single DIBR object. When multiple DepthImage nodes are related to each other, they are rendered as a group and thus should be placed under the same Transform node. The diTexture field specifies the texture with depth (SimpleTexture or PointTexture), which will be associated with the region defined in the DepthImage node.

The OctreeImage node defines an octree structure and its projected textures. The OctreeResolution field specifies the maximum number of terminal leaves of the octree along one side of the surrounding cube. The octree field specifies a set of internal nodes of the octree. Each internal node is represented by one octet. A 1 in the i-th bit of this octet means that child nodes exist for the i-th child of that inner node, while a 0 means that they do not exist. The order of the internal nodes of the octree will be the order of the first amplitude traversal of the octree. The order of eight children of an internal node is shown in FIG. 14 (b). The VoxelImageIndex field contains an array of image indexes assigned to the voxel. In the rendering stage, the color attributed to a terminal leaf of the octree is determined by orthographically projecting the terminal leaf onto one of the images with a specific index. The indices are stored in the manner of the octree: if a specific image can be used for all terminal leaves contained in a specific voxel, the voxel containing the index of the image is output to the stream; otherwise, the voxel containing a fixed 'further subdivision' code is output, which means that the image index will be specified separately for each child of the current voxel (in the same recursive way). If the ImageVoxel Index is empty, then the image indexes are determined during the rendering stage. The images field specifies a set of DepthImage nodes, with SimpleTexture for the diTexture field. However, the NearPlane field and the FarPlane field of the DepthImage node are not used, nor the depth field of the Simple Texture node.

The rendering procedures for DIBR formats are not part of the AFX, but it is necessary to explain the ideas used to achieve the simplicity, speed and quality of the rendering of objects by DIBR. Our rendering procedures are based on splats, small flat patches of color used as 'rendering primitives'. Two approaches outlined below target two different representations: DepthImage and OctreeImage. In our implementation, OpenGL functions are used for splat generation to speed up rendering. However, software representation is also possible, and allows optimized calculation, using the simple DepthImage or OctreeImage structure.

The procedure we use to represent DepthImage objects is extremely simple. It should be mentioned, however, that it depends on the OpenGL functions and that it works much faster with the help of a hardware accelerator. In this procedure, we transform all pixels with depth, from SimpleTexture

ES 2 374 064 T3 and PointTextures to be represented, in three-dimensional points, then we place small polygons (splats) at these points and apply OpenGL representation functions. The pseudo-code of this procedure for the case of SimpleTexture is given in FIG. 28. The case of PointTexture is treated in exactly the same way.

The size of the splat must be adapted to the distance between the point and the observer. We use the following simple approach. First, the surrounding cube of the given three-dimensional object is subdivided into a rough uniform grid. The size of the splat is calculated for each cell in the grid, and this value is used for the points within the cell. The calculation is carried out as follows:

- Represent the cell on the screen by means of OpenGL.

- Calculate the length L of the largest projection diagonal (in pixels).

- Estimate D (splat diameter) as, where N is an average number of points per cell side, and C is a heuristic constant, approximately equal to 1.3.

We would like to emphasize that this procedure could certainly improve with more precise calculations of the radius, more complex splats and generation of antialiases. However, even this simple approach provides good visual quality.

The same approach works for OctreeImage, where the octree nodes at one of the coarser levels are used in the above splat size calculations. However, for Octree Image the color information should first be associated with the set of voxels. This can be done very easily, because each voxel has its corresponding reference image index. The position of pixels in a reference image is also known during octree flow parsing. As the colors of the OctreeImage voxels are determined, the splat sizes are estimated and OpenGL-based rendering is used, as described above.

The DIBR formats have been implemented and tested on various three-dimensional models. One of the models ("Tower") was obtained by scanning a real physical object (a Cyberware color 3D scanner was used), the others were converted from the 3DS-MAX demo package. The tests were carried out on a computer with a 1.8 GHz Pentium-IV, with an OpenGL accelerator.

In the following subsections, we explain the procedures for converting polygonal formats to DIBR formats, and then we present the modeling, representation, and compression results of the different DIBR formats. Most of the data is for DepthImage and OctreeImage models; these formats have animated versions and can be effectively compressed. All the models presented have been built with the orthographic camera, since, in general, it is the preferable way to represent compact objects. Note that the perspective camera is used mostly for DIBR's inexpensive representation of distant environments.

The generation of the DIBR model begins with obtaining a sufficient number of SimpleTextures. For a polygonal object, Simple Textures are calculated, while for the real-world object, the data is obtained from digital cameras and scanning devices. The next stage depends on the DIBR format we want to use.

The DepthImage is simply a union of the obtained SimpleTextures. Although depth maps can be stored in compressed form, only lossless compression is acceptable, as even small distortion in geometry is often highly noticeable.

Reference images can be stored in lossy compressed form, but in this case pre-processing is required. While it is generally tolerable to use popular procedures such as JPEG lossy compression, borderline distortions become more noticeable in 3D object views generated especially due to the boundaries between the object and the background of the reference image, where the color background appears to 'spill over' onto the object. The solution we have used to tackle the problem is to stretch the image in the border blocks towards the background, using the average block color and rapid intensity decay, and then apply JPEG compression. The effect resembles 'squashing' the distortion towards the background, where it is harmless, as the background pixels are not used for rendering. Internal boundaries in lossy-compressed reference images can also cause distortions, but these are generally less visible.

To generate OctreeImage models, we use a point-based intermediate representation (PBR). The set of points that constitute the PBR is the union of the colored points obtained by the displacement of pixels in reference images, at distances specified in the corresponding depth maps. The original SimpleTextures should be constructed in such a way that the resulting PBR provides a sufficiently accurate approximation of the surface of the object. After that, the PBR becomes the OctreeImage, as outlined in FIG. 24, and is used to generate a new complete set of reference images that satisfy the constraints imposed by this format. At the same time, the additional data structure IndexImagenVoxel is generated, which

ES 2 374 064 T3 represents reference image indices for octree voxels. In case the reference images were stored in lossy formats, they are first pre-processed as explained in the previous subsection. Furthermore, since the structure of the TBVO explicitly specifies the pixel containing its color for each voxel, redundant pixels are discarded, further reducing the volume of VoxelImageIndex. Examples of the reference images, original and processed in the JPEG format, are shown in FIG. 29.

Note that the quality degradation due to lossy compression is negligible for Octree Images, but is still sometimes noticeable for DepthImage objects.

PointTexture models are built using the projection of the object onto a reference plane, as explained in Section 2.1. If this does not produce enough samples (which may be the case for surface parts almost tangent to the projection vector), additional SimpleTextures are constructed to provide more samples. The obtained set of samples is then rearranged into the PointTexture structure.

The data on rendering speed will now be presented.

The rendering speed of the “Palmera512” DepthImage is around 2 frames per second (note that there are 21 Simple Textures), while other static models that we tested with a reference image size of 512 are represented with between 5 and 6 frames per second. Note that the rendering speed depends mostly on the number and resolution of the reference images, but not on the complexity of the scene. This is a major advantage over polygonal representations, especially in the animated case. The animated OctreeImage “Dragon512” is displayed at the rate of 24 frames per second (fps).

The "Angel256" DepthImage model is shown in FIG. 22. FIGs. 30 to 34 show various other DIBR and polygonal patterns. FIG. 30 compares the appearance of the “Morton”, polygonal, and DepthImage model. The DepthImage model uses reference images in the JPEG format, and rendering is done by the simplest generation of splats, described in Section 5, but the image quality is quite acceptable. FIG. 31 compares two versions of the scanned "Tower" model. Black dots at the top of the model are due to noisy input data. FIG. 32 demonstrates a more complex "Palm Tree" model, made up of 21 Simple Textures. It also shows good quality, although the end sheets are generally wider on the original 3DS-MAX, which is a consequence of the simplified generation of splats.

FIG. 33 presents a three-dimensional plot of the animation of the Octree Image “Dragon512”. FIG. 34 demonstrates the ability of a DotTexture format to provide excellent quality patterns.

The depth image based node structure according to the present invention includes the SimpleTexture node, the PointTexture node, the DepthImage node and the OctreeImage node. The DepthImage node is made up of depth information and a color image. The color image is selected between the SimpleTexture node and the PointTexture node.

When an object is viewed from six points of view (front, background, plane, rear, left and right sides), the object can be represented by six pairs of SimpleTexture nodes. The specification of the SimpleTexture node is shown in FIG. 26.

With reference to FIG. 26, the SimpleTexture node is composed of a Texture field in which a color image containing the color for each pixel is recorded, and a depth field in which the depth for each pixel is recorded. The SimpleTexture node defines a single IBR texture. Here, a texture means a colored flat image.

A flat image, which contains the color for each pixel that makes up the image, is in the texture field. The depth for each pixel that makes up the image is recorded in the depth field. A set of depths in the depth field forms the depth images corresponding to the flat image in the texture field. Depth images are flat images represented in gray scales, depending on the depths. In the case of a video format for generating animated objects, the depth information and the color information are multiple sequences of image frames.

The flat image in the texture field (that is, the colored image) and the flat image in the depth field (that is, the image rendered in grayscale) constitute a SimpleTexture node. FIG. 20 shows “Morton” objects represented by SimpleTexture nodes for front viewpoints. In conclusion, the objects are represented by six nodes of SimpleTexture, which are pairs of images generated for six points of view. FIG. 22 displays “Angel” objects represented by six SimpleTexture nodes.

The color image can be represented with PointTexture nodes. FIG. 21 shows Point textures generated by projecting an object onto a reference plane (in this case, a plane separated by a predetermined distance from the object, to face the back face of the object).

ES 2 374 064 T3

FIG. 26 also shows the specification of a PointTexture node. With reference to FIG. 26, a PointTexture node is made up of a size field, a resolution field, a depth field, and a color field. The size information of an image plane is recorded in the size field. The size field is made up of width and height fields, where the width and height of the image plane are recorded respectively. The size of the image plane is set to a size sufficient to cover the entire object projected onto the reference plane.

Resolution information about depth for each pixel is recorded in the resolution field. For example, when a number "8" is recorded in the resolution field, the depth of an object is represented with 256 scales, based on the distance from the reference plane.

Multiple elements of depth information about each pixel are recorded in the depth field. The depth information is a sequence of pixel numbers projected onto the image plane and the depths for the respective pixels. Color information about each pixel is recorded in the color field. Color information is a sequence of colors corresponding to the respective pixels projected onto the image plane.

The point of view information that makes up the DepthImage node includes various fields such as point of view, visibility, projection, procedure, or distance.

In the viewpoint field, the viewpoints from which an image plane is viewed are registered. The point of view field has position and orientation fields, where the position and orientation of the point of view are recorded. The position in the position field is a relative location of the point of view with respect to the origin (0, 0, 0) of the coordinate system, while the orientation in the orientation field is a magnitude of rotation of the point of view with relative to the default orientation.

In the field of view, an area of visibility is recorded from the point of view to the image plane. In the field of projection procedure, a projection procedure is recorded from the point of view to the image plane. In the present invention, the projection method includes an orthogonal projection method in which the area of visibility is represented by width and height, and a perspective projection method, in which the area of visibility is represented by a horizontal angle and a vertical angle. When the orthogonal projection procedure is selected, that is, when the projection procedure field is set to TRUE, the width and height of the visibility area correspond, respectively, to the width and height of an image plane. When the perspective projection procedure is selected, the horizontal and vertical angles of the viewing area correspond to the angles formed with the horizontal and vertical sides by the views varying from one point of view to the image plane.

In the distance field, a distance from a point of view to a closer boundary plane and a distance from the point of view to a further boundary plane are recorded. The distance field consists of a Near Plane field and a Far Plane field. The distance field defines an area for depth information.

FIGs. 35A and 35B are diagrams showing the relationships of the respective nodes when representing an object in a DepthPicture format, with SimpleTexture nodes and PointTexture nodes, respectively.

With reference to FIG. 35A, the object can be represented with sets of DepthImage nodes, corresponding to six viewpoints. Each of the respective DepthImage nodes consists of point-of-view and SimpleTexture information. SimpleTexture consists of a pair of color image and depth image.

With reference to FIG. 35B, the object can be represented with a DepthImage node. The specification of the DepthImage node is described as before. A PointTexture node is made up of plane information, with information about a plane onto which the object is projected, and depth information and color information for various points of objects projected onto the image plane.

In an OctreeImage node, an object is represented by the structure of internal nodes that constitute the voxels that contain the object and the reference images. The specification of the OctreeImage node is shown in FIG. 26.

With reference to FIG. 26, the OctreeImage node includes fields for OctreeResolution, octree, VoxelImageIndex, and images.

In the Octree Resolution field, record the maximum number of terminal octree leaves along one side of the surrounding cube containing the object. In the octree field, an internal node structure is recorded. An internal node is a node for a subcube generated after subdividing the surrounding cube that contains the entire object. The subdivision of each subcube is carried out iteratively to generate 8 subcubes, until a number is reached

ES 2 374 064 T3 default of subcubes. In the case of iteratively performing subdivision 3 times, assuming that a node for a subcube after the second subdivision iteration is mentioned as the current node, a node for a subcube after the first subdivision iteration, and a node for a subcube after the third subdivision they are mentioned as a parent node and a child node, respectively. The order of 8 divided subcubes is given by the order of priority in width. FIG. 14 shows a procedure for assigning subcube priority numbers. Each internal node is represented by one octet. The node information recorded in the bit streams that make up the octet represents the presence or absence of child nodes of child nodes belonging to the internal node.

In the index field, the reference image indexes corresponding to the respective internal nodes are recorded. In the image field, reference images corresponding to the indices recorded in the index field are registered. The reference images are nodes of DepthImage, and their structure is described as before.

FIG. 36 is a diagram showing the structure of a relevant OctreeImage node when representing an object using OctreeImage nodes.

With reference to FIG. 36, the nodes of OctreeImage are encapsulated by bit wrappers. Each bit wrapper includes an OctreeImage node. When an object is rendered in SimpleTexture nodes, the OctreeImage node includes 6 DepthImage nodes, each DepthImage node containing a SimpleTexture node. On the other hand, when an object is rendered with PointTexture nodes, the OctreeImage node includes a single DepthImage node.

The present invention can be implemented on a computer-readable recording medium, by means of computer-readable codes. Computer-readable recording medium includes all kinds of recording apparatus from which data can be read readable by a computer system, and examples thereof are ROM, RAM, CD-ROM, magnetic tapes, floppy disks. , optical data storage devices or the like, and also data made on a carrier wave, e.g. eg, from the Internet or other transmission medium. In addition, the computer-readable recording medium is distributed in a computer system connected with a network, so that the computer-readable codes are stored and implemented by means of a distributed procedure.

According to the present invention, in image-based representations, since the perfect information in a colored three-dimensional object is encoded by means of a set of two-dimensional images - a simple and regular structure instantly adopted in well-known procedures for processing and compression For imaging, the algorithm is simple and can be supported by hardware in many ways. Furthermore, rendering time for image-based models is proportional to the number of pixels in the reference and output images, but generally not to the geometric complexity, as in the polygonal case. Additionally, when image-based rendering is applied to real-world objects and scenes, the photo-realistic rendering of a natural scene is made possible without the use of millions of polygons and expensive calculations.

The preceding description of an implementation of the invention has been presented for purposes of illustration and description. It is not exhaustive and does not limit the invention to the exact form disclosed. Modifications and variations are possible in light of the above disclosures, or may be acquired from practice of the invention. The scope of the invention is defined by the claims and their equivalents.

Contents35

42 members in 8 offices

This recordMember, by publication datePriority claim

Priority claims25

Priority claims
Document	Office	Kind	Date
333167P	United States of America	–	2001-11-27
33316701	United States of America	P	2001-11-27
33316701	United States of America	P	2001-11-27
362545P	United States of America	–	2002-03-08
36254502	United States of America	P	2002-03-08
36254502	United States of America	P	2002-03-08
376563P	United States of America	–	2002-05-01
37656302	United States of America	P	2002-05-01
37656302	United States of America	P	2002-05-01
395304P	United States of America	–	2002-07-12
39530402	United States of America	P	2002-07-12
39530402	United States of America	P	2002-07-12
20020067971	Republic of Korea	A	2002-11-04
20020067971	Republic of Korea	A	2002-11-04
2002067971	Republic of Korea	–	2002-11-04
2002067971	–	–	–
333167P	–	–	–
362545P	–	–	–
376563P	–	–	–
395304P	–	–	–
KR20020067971	–	–	–
US20010333167P	–	–	–
US20020362545P	–	–	–
US20020376563P	–	–	–
US20020395304P	–	–	–

Members42

Family members, oldest first
Document	Office	Kind
CA2413056A1	Canada	A1	2003-05-27
CA2413058A1	Canada	A1	2003-05-27
CA2514655A1	Canada	A1	2003-05-27
CA2517842A1	Canada	A1	2003-05-27
KR20030043637A	Republic of Korea	A	2003-06-02
KR20030043638A	Republic of Korea	A	2003-06-02
EP1321893A2	European Patent Office (EPO)	A2	2003-06-25
EP1321894A2	European Patent Office (EPO)	A2	2003-06-25
CN1430183A	China	A	2003-07-16
CN1432969A	China	A	2003-07-30
JP2003296755A	Japan	A	2003-10-17
US2003214502A1	United States of America	A1	2003-11-20
US2003218606A1	United States of America	A1	2003-11-27
JP2004005373A	Japan	A	2004-01-08
KR100446635B1	Republic of Korea	B1	2004-09-04
RU2237283C2	Russian Federation	C2	2004-09-27
RU2237284C2	Russian Federation	C2	2004-09-27
KR100450823B1	Republic of Korea	B1	2004-10-01
EP1321893A3	European Patent Office (EPO)	A3	2005-01-05
EP1321894A3	European Patent Office (EPO)	A3	2005-01-05
CN1218282C	China	C	2005-09-07
CN1790421A	China	A	2006-06-21
CN1261912C	China	C	2006-06-28
JP2006286024A	Japan	A	2006-10-19
JP2006318503A	Japan	A	2006-11-24
JP3957620B2	Japan	B2	2007-08-15
CA2413056C	Canada	C	2009-02-10
CN100545870C	China	C	2009-09-30
JP2010033594A	Japan	A	2010-02-12
CA2514655C	Canada	C	2010-05-11
JP2010218588A	Japan	A	2010-09-30
JP4629005B2	Japan	B2	2011-02-09
US8022951B2	United States of America	B2	2011-09-20
EP1321893B1	European Patent Office (EPO)	B1	2011-11-09
EP1321894B1	European Patent Office (EPO)	B1	2011-11-09
JP4832975B2	Japan	B2	2011-12-07
CA2413058C	Canada	C	2012-01-17
ES2374064T3This record	Spain	T3	2012-02-13
ES2374066T3	Spain	T3	2012-02-13
US8217941B2	United States of America	B2	2012-07-10
US2012176381A1	United States of America	A1	2012-07-12
US8390622B2	United States of America	B2	2013-03-05

Abstract

Term

ES 2 374 064 T3

DESCRIPTION

ES 2 374 064 T3

1. ISO / IEC JTC 1 / SC 29 / WG 11 MOVIE AND AUDIO ENCODING

ES 2 374 064 T3

ES 2 374 064 T3

II. ISO / IEC JTC 1 / SC 29 / WG 11 MOVIE AND AUDIO ENCODING

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

IV. ISO / IEC JTC 1 / SC 29 / WG 11 - FILM AND AUDIO CODING

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

(IO 01 (-1 O 0 '

O 0 0 10-10

-1 OR 0 '

O 0 '0-10 0 O -1,

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

ES 2 374 064 T3

Priority claims25

Members42

Numbers

Titles2

Classification