EP2135221A1 - Procédé de codage de données répresentatives d'une texture multidimensionnelle, dispositif de codage, procédé et dispositif de décodage, signal et programme correspondants - Google Patents

Procédé de codage de données répresentatives d'une texture multidimensionnelle, dispositif de codage, procédé et dispositif de décodage, signal et programme correspondants

Info

Publication number
EP2135221A1
EP2135221A1 EP08762021A EP08762021A EP2135221A1 EP 2135221 A1 EP2135221 A1 EP 2135221A1 EP 08762021 A EP08762021 A EP 08762021A EP 08762021 A EP08762021 A EP 08762021A EP 2135221 A1 EP2135221 A1 EP 2135221A1
Authority
EP
European Patent Office
Prior art keywords
data
dimensions
texture
wavelet
decomposition
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
EP08762021A
Other languages
German (de)
English (en)
Inventor
Jérôme BARIL
Patrick Gioia
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Orange SA
Original Assignee
France Telecom SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by France Telecom SA filed Critical France Telecom SA
Publication of EP2135221A1 publication Critical patent/EP2135221A1/fr
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G06T9/001—Model-based coding, e.g. wire frame
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
    • H04N19/62—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding by frequency transforming in three dimensions [3D]

Definitions

  • the present invention is in the field of computer graphics, and more specifically in the field of coding and data compression for viewing virtual scenes.
  • the invention relates to a method for encoding multidimensional textures, for transmitting and generating photo-realistic synthetic images.
  • the shape of the surface is placed at the coarsest level, the macroscopic level, and corresponds to the geometry of the object whose surface is represented.
  • this geometry is most often expressed by a mesh, that is to say a set of polygons.
  • BRDF Bilateral Reflectance Distribution Functions
  • An intermediate layer encapsulates geometric details, such as small bumps on a granular surface for example. From an application point of view, this layer is often represented by a method called normal disturbances or "bump mapping", or by a method of geometric variation of the points of the mesh along their normal, called “Displacement mapping” method. This level disturbs the upper layer because the local variations of the surface cause a local variation in light intensity, due to the creation of an occlusion or a shadow for example.
  • BTF Bilateral Texture Functions
  • BTF BTF (x, y, ⁇ v , ⁇ v , ⁇ !, ⁇ l )
  • - x and y represent spatial coordinates expressed in parametric coordinates
  • - ⁇ v and ⁇ v define the direction of a point of view in polar coordinates
  • a BTF thus corresponds to a set of images where each image is associated with a point of view and a direction of light.
  • This capture method makes it possible to model both the mesostructure, the micro-structure and all the interactions that exist between these two layers, for the same material.
  • fine sampling is necessary, ie a BTF corresponds to a large number of images.
  • the first approach is to approximate a multidimensional texture by continuous function models.
  • a texture expressed as a BTF is approximated by BRDF function models, or by bi-quadratic polynomials.
  • this BTF being expressed by a set of images, each being the photograph of the surface of a material corresponding to the texture according to a given point of view and direction of light, classifying differently these data is obtained for each pixel its variation according to the direction of the light considered and according to the point of view considered.
  • this BTF is approximated by a set of BRDF function models:
  • z is the projection of the spatial coordinates x and y initially defining a pixel in the BTF, on a single dimension
  • v is the projection of the initial polar coordinates ⁇ v and ⁇ v initially defining the direction of a point of view in the BTF, on a single dimension
  • - / is the projection of the initial polar coordinates ⁇ , and ⁇ , initially defining a direction of light in the BTF, on a single dimension
  • BRDF z (v, I) is a BRDF function model for the z pixel, in which the direction of light and the direction of a point of view are each expressed in a single dimension.
  • v is the projection of the polar coordinates ⁇ v and ⁇ v initially defining the direction of a point of view in the BTF, on a single dimension
  • the approximation-based methods according to this first approach make it possible to obtain a compact and continuous representation of the textures, which adapts well to the current rendering algorithms, generally carried out directly on programmable graphic cards. However, they are limited by the complexity of the calculations required. Indeed, if a singular value decomposition of a BTF is sufficient to obtain an approximation by bi-quadratic polynomials, the approximation of the same function by BRDF function models is often very complex. Moreover, these approximations do not make it possible to make the variety of the effects captured during the acquisition of the BTFs. Effects related to light-wise or light-directional displacements would require, to be taken into account, the use of even more complex BRDF function models, or different polynomials, as described in the articles:
  • This method consists in finding the directions in space that best represent the correlations of the dataset constituted by the BTF.
  • a new base is then defined, resulting from the orthogonalization of the analysis domain by a search of the eigenvectors and eigenvalues of the covariance matrix associated with the BTF.
  • the axes of the new associated marker are such that the variance of the initial samples of the BTF is maximum.
  • the eigenvectors are then sorted in order of importance, according to their corresponding eigenvalues, in descending order. We keep only the most influential axes.
  • the initial data of the BTF are then projected in this new space of reduced dimensions. We thus obtain, by linear combination, an approximation of the original signal in this new base:
  • PCA Component Analysis
  • CGI Computer Graphics International
  • a spatial tensor represents the projection of the spatial coordinates JC and y on a single dimension
  • a tensor linked to the point of view represents the projection of the polar coordinates ⁇ v and ⁇ v on a single dimension
  • a tensor related to the direction of light represents the projection of the polar coordinates ⁇ , and ⁇ , on a single dimension.
  • the methods based decomposition according to this second approach improve the qualitative results compared to the methods based approximation, the choice of the number of principal components determining the quality of the textures compressed by such methods. They further define a compact and discrete representation of multidimensional textures. This compactness is due to the fact that the vectors resulting from the decomposition are ranked in order of importance and only the most representative vectors are taken into account. However this decimation is random and does not allow to define which details will be hidden during the transformation. It also avoids certain singularities captured during the acquisition process, the substituted axes corresponding to zones of weak correlation. This lack of frequency information limits the flexibility of these methods: they do not make it possible to directly provide a representation according to different levels of detail, by a progressive decoding of the information.
  • a multi-resolution representation of the textures compressed by these methods requires, as in the article "Level-of-detail representation of bidirectional texture functions for real-time rendering", additional transformations.
  • the decomposition-based multi-resolution method mentioned in this article actually produces a texture representation by resolution and therefore does not correspond to a single multi-resolution representation allowing progressive decoding of the information based on a choice of resolution.
  • the existing methods of texture compression therefore do not allow to preserve all the captured details of a texture, nor to provide a progressive decoding of the texture information in order to adapt to the material constraints during the transmission of this texture.
  • information for example related to the power of the graphics cards receivers or network throughput used.
  • this ability is necessary to generalize the use of textures to decentralized systems or to a wider range of devices, such as mobile devices.
  • the present invention aims to solve the disadvantages of the prior art by providing in particular a method and a data encoding device representative of a multidimensional texture, using the properties of the wavelet analysis on all dimensions of this texture.
  • the invention proposes a method for encoding data representative of a multidimensional texture, said data being initially organized on a number of dimensions at least equal to three, at least one of said dimensions being linked to a rendering parameter of said texture, characterized in that it comprises the steps of:
  • the compression ratio obtained is better than in the prior art, while keeping a good level of detail and requiring only a small calculation complexity, This allows to rebuild in real time the initial data during rendering.
  • multilinear algebra is sometimes expensive during synthesis, ie say during decoding, the tensors used in the invention are hollow, that is to say that most of their coefficients are zero, which, in practice, involves few calculations.
  • the high compression ratio obtained by the coding method according to the invention makes it possible to maintain a texture representation of very good quality, which in particular retains all the effects related to the displacement of the point of view or the direction of the light.
  • the wavelet analysis corresponds to a frequency analysis of an initial signal, which is broken down into frequency bands. As a result, it is possible to target the decimation frequency and this for each dimension of the signal. This makes it possible to preserve all the singularities of the compressed texture according to the invention.
  • This analysis is also a multi-resolution analysis, it produces a representation of the initial signal by scale, in which one qualifies of coarser level the coefficients low-frequency and of the finest level the reconstruction starting from the coefficients high-frequency . This feature allows you to define different levels of detail from a single texture representation.
  • Another advantage related to wavelet analysis is to make the coding according to the invention extremely configurable: according to whether a representation of the best possible quality or a most compact representation is preferred, a lossless or lossy compression.
  • the coding method according to the invention is compatible with the "peer-to-peer” virtual navigation systems, which require fault-tolerance and great flexibility of information transmission. In particular, it makes it possible to transmit texture data from different transmitters in parallel to receivers of very different capacities.
  • the coding method according to the invention allows dynamic and fast access to texture data coded according to the invention. Indeed, it is not necessary to reconstruct the set of initial data to each new image of the same texture when rendered, because the coding of the data according to the invention allows a local reconstruction of areas of interest.
  • the coding method according to the invention comprises a preliminary step of reorganization of said data representative of a multidimensional texture according to a predetermined number of dimensions.
  • This reorganization step of the texture data makes it possible to simplify the wavelet decomposition, by reducing the number of dimensions in particular.
  • said data are arranged so as to maximize the correlation between two successive samples of said data in at least one dimension.
  • said data representative of a multidimensional texture represent colors according to the YUV color coding system.
  • YUV color coding system instead of a conventional red / green / blue RGB coding system, to represent the colors of the coded texture according to the invention, makes it possible to obtain, for an equivalent visual quality, better compression rates. Indeed, since the human eye is less sensitive to chromatic variations and more to luminance, this choice makes it possible, during the quantization step associated with the coding, to code less precisely the parameters U and V representative of the chromaticity, than the parameter Y representative of the luminance.
  • the compression step of the coding method according to the invention uses a "zerotree" type coding.
  • This type of coding makes it possible to optimize the compression of the texture data that has been analyzed in wavelets.
  • the invention also relates to a method for decoding data representative of a multidimensional texture, said data being initially organized on a number of dimensions at least equal to three, at least one of said dimensions being linked to a rendering parameter of said texture, characterized in that it comprises the steps of: - decompression of said data, and wavelet synthesis on said data dimensions obtained from said decompression.
  • the invention also relates to a signal representative of a multidimensional texture initially represented by data organized on a number of dimensions at least equal to three, at least one of said dimensions being linked to a rendering parameter of said texture, characterized in that said data has been encoded by wavelet analysis on said dimensions, and then by compression of data obtained from the result of said analysis.
  • the invention further relates to a device for encoding data representative of a multidimensional texture, said data being initially organized over a number of dimensions of at least three, at least one of said dimensions being linked to a rendering parameter of said texture, characterized in that it comprises: - wavelet analysis means of said data on said dimensions,
  • the invention also relates to a device for decoding data representative of a multidimensional texture, said data being initially organized on a number of dimensions of at least three, at least one of said dimensions being linked to a rendering parameter of said texture, characterized in that it comprises:
  • the decoding method, the signal, the coding device and the decoding device have advantages similar to those of the coding method according to the invention. 1 0
  • the invention finally relates to a computer program comprising instructions for implementing the coding method according to the invention or the decoding method according to the invention, when it is executed on a computer.
  • FIG. 1 represents the sampling of the acquisition of a BTF modeling a texture
  • FIG. 2 is a table illustrating the values of this sampling
  • FIG. 3 represents an interpretation of this BTF
  • FIG. 4 represents an embodiment of the coding method and the decoding method according to the invention
  • FIG. 5 represents steps of the coding method according to the invention, as described in this embodiment,
  • FIG. 6 represents a level of wavelet decomposition of texture data
  • FIG. 7 represents a wavelet decomposition of texture data
  • FIG. 8 represents a decomposition tree in wavelet packets of texture data
  • FIG. 9 represents the allocation of costs to the elements of this decomposition in wavelet packets
  • FIG. 10 represents another decomposition tree in texture data wavelet packets
  • FIG. 11 represents a coded texture data representation format according to the invention
  • FIG. 12 represents steps of the decoding method according to the invention as described in this embodiment.
  • the coding method according to the invention is used to compress a multidimensional texture expressed in the form of a six-dimensional BTF.
  • wavelet decomposition can be generalized to any number of dimensions
  • the method according to the invention is also applicable to multidimensional textures represented differently, for example in the form of a four-dimensional "Polynomial Texture Map" or "Time-varying BTF". "in seven dimensions.
  • the BTF expressing this texture is the result of an acquisition process shown in Figure 1.
  • the BTF is sampled according to a hemisphere of shots.
  • each point of the texture is thus photographed in a polar coordinate point of view direction ⁇ v and ⁇ v , and in a direction of the light of polar coordinates ⁇ and ⁇ .
  • the table TAB of FIG. 2 indicates the number of photographs taken for a given latitude ⁇ v or ⁇ .
  • the angle ⁇ v varies from 72 degrees to 72 degrees, which corresponds to 5 photographs taken for this latitude.
  • FIG. 3 illustrates this interpretation of the BTF: each of the images I of these 6400 images represents the texture in parametric coordinates x and y, and corresponds to a point of view direction ( ⁇ Vl ⁇ v ) and a direction of light ( ⁇ , q> ⁇ ).
  • the coding method according to the invention uses wavelets which are obviously wavelets of the "second generation" type, because the wavelets of the first generation are not suitable. to this type of sampling.
  • the images I forming the data of the BTF are stored in a database BDD shown in FIG. 4, the coding method according to the invention being implemented in this embodiment in a software manner in a computer ORD having access to this database. of data.
  • the calculations necessary for the coding method according to the invention are carried out in the CPU of the computer ORD. As a variant, given the importance of the size of the data on which the calculations necessary for their coding are performed, these calculations are carried out on several computers operating in parallel.
  • the coding method according to the invention is represented in the form of an algorithm comprising steps C1 to C3.
  • the first step C1 is a reorganization of the data of the BTF whose data are initially organized in six dimensions, in a reduced number of dimensions, so as to limit the complexity of the calculations.
  • this number of dimensions depends on the applications using the compressed data, depending on whether less complex calculations or a higher compression ratio are preferred. In fact, the more dimensions we keep, the more we exploit the inter-dimensional coherence and the more 1 es
  • BTF (x, y, ⁇ v , ⁇ v , ⁇ ,, ⁇ ,) BTF (x, y, v, /),
  • v is the projection of the initial polar coordinates ⁇ v and ⁇ v initially defining the direction of a point of view in the BTF, on a single dimension
  • / is the projection of the initial polar coordinates ⁇ , and ⁇ t initially defining a direction of light in the BTF, in one dimension.
  • the BTF data is not rearranged, wavelet analysis is then done in six dimensions.
  • two types of wavelets are used, for example: non-separable two-dimensional wavelets in order to adapt the analysis filters to the sampling of the BTF according to the point of view and the light directions , and separable one-dimensional wavelets for spatial analysis.
  • the initial data of the BTF are rearranged in three dimensions according to a decomposition called "reflectance field", that is to say that it is expressed by point of view v and that the direction of the light is projected on one dimension:
  • BTF (x, y, ⁇ v , ⁇ v , ⁇ ⁇ , ⁇ ,) ⁇ BTF v (x, y) ⁇ , Vv
  • the data of the BTF are rearranged in five dimensions, the direction light being projected on one dimension:
  • BTF (x, y, ⁇ v , ⁇ v , ⁇ ⁇ , ⁇ ⁇ ) BTF (x, y, ⁇ v , ⁇ v , l)
  • the projection v corresponding to the doublet ( ⁇ v , ⁇ v ) is ranked in ascending order according to ⁇ v and ⁇ v , that is to say that according to the dimension of the point of view v the images I are classified in the following order of sampling: (0,0), (15,0), (15,72) I ..., (75,345).
  • the projection / corresponding to the doublet ( ⁇ ,, ⁇ t ) is ranked in increasing order according to ⁇ , and ⁇ ,.
  • the images I are classified so as to maximize the correlation between two successive images in the direction of light.
  • This classification is performed for example in the following manner on all the images having in common the same point of view:
  • a root image is chosen from this set, for example the projection image corresponding to the doublet (0,0) in polar coordinates,
  • the next image is then iteratively searched from the previous image, this image corresponding to the image minimizing the difference between the previous image and the set of images that have not already been classified.
  • This classification of the images I in order of likelihood along the axis corresponding to the projection /, allows in the following to improve the compression during the step C3.
  • BTF data is coded for RGB acquisition.
  • this color coding format does not make it possible to exploit the perception factor to its maximum.
  • a change of RGB color space towards the color space YUV is preferably carried out, where Y represents the luminance, and U and V the chrominance. .
  • This change has an impact on the continuation of the treatment because the utility of such a modification is to provide a larger quantity of information for the luminance with respect to the chrominance during the quantification in step C3. 2
  • the second step C2 of the coding method is the wavelet analysis of the data thus reorganized and reformatted, on the four dimensions chosen in step C1.
  • wavelet analysis means that a wavelet or wavelet packet signal is broken down into successive wavelet transforms. A wavelet analysis therefore covers at least one wavelet decomposition.
  • This wavelet decomposition is done according to the organization chosen in step C1.
  • the use of second-generation wavelets is necessary because of irregular sampling intervals and border areas. It should also be noted that even assuming that new samples are synthesized in step C1 in order to regularize these intervals, the analysis domain still being limited, the second generation wavelets are still necessary.
  • step C1 if the BTF data has been rearranged in step C1 by a number of dimensions greater than four, the calculations are weighted during the wavelet decomposition to transform an irregular interval into a regular interval and back to the case. regular figure. This weighting makes the wavelet decomposition more faithful to reality, that is to say that during decompression the decompressed data make it possible to synthesize new, very realistic texture views.
  • wavelet base more complex, higher order. This allows, however, at the cost of more complex calculations and longer, to maintain despite compression a texture representation of very good resolution.
  • bi-orthogonal wavelets which are practical for their ease of construction via the "lifting scheme” method, or geometric wavelets are used, considering the spatial configuration of the texture as a geometry in a space of the same dimension.
  • mesh-based wavelets using the quadrilateral as primitive, and applying conventional subdivision techniques such as the "Butterfly" technique.
  • the basic use of wavelets having two zero moments is a good compromise to reconcile quality of restitution and speed of calculation.
  • the wavelet decomposition in step C2 is performed at each decomposition level according to the diagram of FIG. 6.
  • S J be the signal formed by the set of data ⁇ s ⁇ J , mn ⁇ of the jth wavelet decomposition level in the Haar base, reorganized data obtained at the end of step C1, and wherein:
  • k is an index representing the kth value of the signal along the axis of the spatial coordinate x
  • p is an index representing the p-th value of the signal along the axis of the spatial coordinate y
  • - m is an index representing the mth value of the signal along the axis of the projection /
  • n is an index representing the nth value of the signal along the axis of the projection v.
  • the decomposition is done dimension by dimension, by block of data each corresponding to the set of values of the BTF according to one dimension, when each of the three other dimensions is fixed to a given value.
  • the order of processing of these dimensions is chosen according to the correlation of the data of the BTF.
  • the spatial correlation of the texture being stronger than its correlation during a change of direction of the light, itself stronger than during a change of direction of point of view, the wavelet decomposition is carried out first following the index k, then following the index p, then following the index m and finally following the index n.
  • the signal S J is first subjected along the axis of the spatial coordinate x to the following functions:
  • the low-pass filter h performs the averages of the data ⁇ s k J pmn ⁇ according to the direction in question, which produces the data ⁇ s ⁇ J pmn ⁇ defined by:
  • the decomposition takes place according to the method of the "lifting scheme", which means for the decomposition in the Haar base that the difference between two values of the signal S J is first calculated and then the sum is calculated. of these two values from this difference:
  • the local character of the wavelet decomposition allows the decomposition to be performed "out of core", that is to say that all the data to be processed is not entirely contained in the main memory. This character also allows data to be processed in parallel by multiple processors.
  • the field of analysis does not need to be segmented to be treated in its entirety.
  • the data ) are then subjected to the same functions but according to the index p: 5 - the operator s separates the data ⁇ s k J ! p ' mn ⁇ and the data [d k J ? pnm ⁇ according to their even or odd indices, the filter h produced from the data ⁇ s k ' pmn ⁇ the data ⁇ s k J ', p . mn ⁇ and from the data ⁇ d k J f pm ⁇ ⁇ the data ⁇ d k J f p ', mn ⁇ ,
  • the filter h produced from the data ⁇ s k Jh p , mn ⁇ , the data ⁇ s k J ! p "! m ',” ⁇ defined by: - and the filter g produced from the data defined by: f j jhltg _ ⁇ h _ ⁇ rjhh
  • the filter h performs the averages of data ⁇ S ym k J ', n ⁇ according to the index n, which produces the data ⁇ s / ⁇ y ** ⁇ defined by: ojhhh, Qjhhh ⁇ j hhhh _ ° k. 'p : mX2n') " * " J * ', pW (2fl' + 1) ⁇ k'p'm'n ' ⁇ j
  • the filter g calculates the differences between the data ⁇ s ⁇ ,. ⁇ according to the index n, which produces the data defined by:
  • the set of data produced during this last decomposition according to the index n forms the result of the wavelet decomposition of the signal S J , ie the data of the at least one wavelet decomposition level of the data obtained at the end of the wavelet decomposition. step C1.
  • We distinguish in this result the data low-frequency low-resolution, and other data that form a signal J ⁇ ⁇ of higher frequency.
  • the decomposition detailed above is a conventional wavelet decomposition of the initial signal S J formed from the data obtained in step C1.
  • this decomposition shown in FIG. 7 only the low frequency signal S J ⁇ ⁇ is re-decomposed at the next decomposition level, the detail signal d J ⁇ ⁇ being retained.
  • the signal S J "x is decomposed into wavelets and produces a signal S J ⁇ 2 of lower frequency that the signal S J ', and a signal J ⁇ 2 of lower frequency than the signal J ⁇ ⁇ and at the decomposition level following the signal S J ⁇ 2 is itself decomposed into wavelets and so on.
  • the last wavelet decomposition on the signal S 1 produces the signals d 0 and S 0 .
  • the data obtained at the end of the step C1 being the images I coded according to the YUV format and classified according to 80 directions of viewpoint and 80 directions of the light, supposing that these images are of resolution 256 * 256, one s for example, stops after three levels of wavelet decomposition.
  • the result of the wavelet analysis is then formed of the signals S 0 , and d ° to d J ⁇ ⁇ where J is three.
  • the 5 ° low frequency signal contains 10 * 10 * 32 * 32 colors coded in the YUV color space.
  • step C2 in order to code the texture optimally, in this step C2 the data obtained at the end of step C1 are broken down into wavelet packets.
  • This decomposition is represented on the tree of FIG. 8.
  • the root of the tree corresponds to the initial signal S J containing the data obtained at the end of step C1.
  • the next level is the result of a wavelet transformation iteration, i.e., the low frequency signal S i and the high frequency signal I x .
  • the recursive decomposition of these signals completes the lower levels of the tree.
  • the decomposition of the signal S J ⁇ X gives two signals S J ⁇ 2 and d J ⁇ 2
  • the decomposition of the signal d Ix also gives two signals S ⁇ J ⁇ and d ⁇ .
  • This decomposition into wavelet packets makes it possible to choose an optimal decomposition tree according to a given criterion, such as entropy of the coding, a predetermined threshold, or the distortion generated by the coding. For this we assign a cost function to each wavelet decomposition, that is, say at each node of the tree shown in Figure 8. This cost function corresponds to the criterion chosen to optimize the tree.
  • the value of the cost function at the decomposition node corresponding to the signal S J is:
  • the decomposition into wavelet packets will stop on the left branch of the tree at the signals S J ⁇ 2 and d J ⁇ 2 , which will not be decomposed, because the sum of their costs is greater than or equal to the cost of their parent signal S J ⁇ ⁇ .
  • the value of the cost function at the decomposition node corresponding to the signal S J is:
  • This cost function defines Shannon's entropy, which measures the amount of information, that is, different coefficients in a decomposition. This criterion is useful for the coding method according to the invention because it keeps the decomposition of lower entropic cost.
  • the wavelet analysis performed at this step C2 is an integer decomposition into wavelets or an entire decomposition into wavelet packets.
  • Such a method is described in the article "Reversible image compression via multi-resolution representation and predictive coding,” by A. Said and W. Pearlman, published in 1993 at an international conference “Visual Communications and Image Processing ". This further optimizes the wavelet analysis by limiting the size of the result of this analysis. Indeed, the data from the analysis are thus represented with fewer resources, the size in bytes of an integer being smaller than that of a decimal number.
  • any wavelet basis can be modified to perform such an entire decomposition. For example, the transformation by Haar rondelette of the signal S J according to the index k becomes:
  • step C3 of the coding method according to the invention is the compression of the data obtained at the end of step C2, the result of the wavelet analysis of the BTF data reorganized and reformatted in step C1.
  • this compression uses a so-called coding
  • a coefficient of the signal d J ⁇ 2 should be related to a coefficient in each of the 16 signals from the decomposition of the signal J ⁇ ⁇ .
  • the signal S ⁇ 1 issuing from this decomposition is itself re-decomposed, in particular into a signal Si / ⁇ - ⁇ of level coarser than that of the signal d J ⁇ 2 .
  • the coefficients of the signals S ⁇ 1 and d ⁇ are related, not to the coefficients of the signal J ⁇ 2 , but to the coefficients of the signal J ⁇ % .
  • a bit stream is obtained which encodes the wavelet packet decomposition performed in step C2.
  • the data thus obtained are much smaller in size than at the end of step C2. Indeed, the fact of exploiting the decrease of the coefficients across the scales, added to the fact that the wavelet analysis produces numerous coefficients close to zero, allows the "zerotree” coding method to obtain a high rate of compression.
  • the data obtained are organized in order of importance, as shown in Figure 11.
  • the ZTO data encode coefficients corresponding to the coarsest level of detail, while the data ZT 1 encodes detail coefficients at a somewhat less coarse level, the ZT2 data of the detail coefficients at an even finer level, and so on.
  • ZTO data is information that best describes the original data.
  • a progressive representation of the texture is available insofar as the data after the ZTO data makes it possible to progressively refine the coarse representation of the texture contained in these ZTO data.
  • a coarse representation of the texture is obtained.
  • this step C3 instead of using a "zerotree” coding, a “dynamic Huffman 11 " type coding combined with a non-uniform scalar quantization is used, in particular the Y component of the data resulting from the step C2 is less quantified than the components U and V.
  • the pitch of this quantization is for example adequately fixed for a fixed compressed data size.
  • This process called “Rate Allocation”, is used in the standard "Joint Photography Experts Group (JPEG
  • JPEG Job Photographic Experts Group
  • the quantization step is calculated iteratively until the desired compression ratio is reached.
  • This aftertreatment is useful for example when transmitting the compressed data over a network at a fixed rate.
  • such a quantification is adaptable in order to quantify less certain areas of interest of the texture, if such zones are identified, compared to other zones of lesser interest.
  • the terminal T Upon reception of the data flow F, the terminal T stores in memory all the data received, or only the first data, for example the data ZTO, ZT 1 and ZT2 if the terminal T has a limited memory capacity, or if a failure communication stops the sending of data just after sending the ZT2 data.
  • the terminal T after channel decoding of the signal carrying the data stream F, decodes the data received according to the steps D1 to D3 shown in FIG. 12.
  • the step D1 is the decompression of the received data.
  • the terminal T uses a "zerotree" decoding algorithm inverse to that used in step C3 for coding, that is to say that it uses the same rules for associating the coefficients of a level of resolution to another to retrieve data from wavelet packet decomposition. If only the data ZTO, ZT1 and ZT2 are decompressed, only the coefficients of the first resolution levels of the wavelet packet decomposition of the step C2 are obtained.
  • the terminal T is able to decode only a portion of the data received, for example to make the texture only in certain directions of viewpoints or certain directions of light.
  • Step D2 is the wavelet synthesis of the decompressed data in step D1. Since the "zerotree" coding is a function of the structure of the wavelet packet decomposition tree retained in step C2, the terminal T easily reconstitutes all or part of the reordered texture data and reformatted at the end of step C1. All that is required is to perform inverse Haar transforms in the order of wavelet packet decomposition, dimension by dimension.
  • step D3 is the six-dimensional reorganization of the data obtained at the end of step D2.
  • the terminal T thus obtains a texture expressed in the form of a BTF 1 that can be used directly to render it on a screen. If only the data ZTO, ZT1 and ZT2 were synthesized in step D2, this BTF is in fact a rough representation of the compressed texture according to the invention.

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Signal Processing (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)
  • Compression Of Band Width Or Redundancy In Fax (AREA)
  • Image Generation (AREA)

Abstract

L'invention concerne un procédé de codage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte les étapes de: analyse (C2) en ondelettes desdites données sur lesdites dimensions; et compression (C3) de données obtenues à partir du résultat de ladite analyse.

Description

Procédé de codage de données représentatives d'une texture multidimensionnelle, dispositif de codage, procédé et dispositif de décodage, signal et programme correspondants
La présente invention se situe dans le domaine de l'informatique graphique, et plus précisément dans le domaine du codage et de la compression de données permettant de visualiser des scènes virtuelles. L'invention concerne en effet un procédé de codage de textures multidimensionnelles, servant à la transmission et à la génération d'images de synthèse photo-réalistes.
Représenter l'apparence des surfaces réelles est une des principales problématiques en informatique graphique. L'apparence globale d'une surface est souvent définie à différentes échelles.
La forme de la surface est placée au niveau le plus grossier, le niveau macroscopique, et correspond à la géométrie de l'objet dont on représente la surface. De par le mode de rendu actuel sur un matériel graphique, cette géométrie est le plus souvent exprimée par un maillage, c'est-à-dire un ensemble de polygones.
Le niveau le plus fin, correspondant à la micro-structure, détermine la manière dont la surface interagit avec son environnement. Elle exprime les propriétés d'un matériau : une surface en bois ne va pas réfléchir la lumière de la même manière qu'une surface métallique. Ces interactions sont représentées en informatique graphique par les Bilatéral Réflectance Distribution Functions (BRDF), fonctions en quatre dimensions dépendantes du point de vue et de la direction de la lumière.
Une couche intermédiaire, la méso-structure, encapsule les détails géométriques, tels que de petites bosses sur une surface granuleuse par exemple. D'un point de vue applicatif, on représente souvent cette couche par une méthode dite de perturbations des normales ou "bump mapping", ou encore par une méthode de variation géométrique des points du maillage le long de leur normale, appelée méthode de "Displacement mapping". Ce niveau perturbe la couche supérieure car les variations locales de la surface entraînent une variation locale de l'intensité lumineuse, du fait de la création d'une occlusion ou d'une ombre par exemple.
En capturant le rendu de la surface, à l'aide d'un appareillage photonumérique, suivant plusieurs points de vue et plusieurs directions de la lumière, le calcul complexe des interactions entre méso-structure et micro- structure, nécessaire afin d'effectuer le rendu d'une surface, est contourné. On obtient ainsi des fonctions appelées "Bilatéral Texture Fonctions" (BTF), décrites dans l'article de KJ. Dana, B. van Ginneken, S. K. Nayar et JJ. Koenderink, intitulé "Réflectance and texture of real-world surfaces", et publié dans le journal " Association for Computer Machinery (ACM) Transactions On Graphics" en 1999. On exprime ces fonctions par exemple sous la forme:
BTF = BTF(x,y,θv,φv,θ!,φl) où:
- x et y représentent des coordonnées spatiales exprimées en coordonnées paramétriques, - θv et φv définissent la direction d'un point de vue en coordonnées polaires,
- et θ, et φι définissent une direction de la lumière en coordonnées polaires.
Une BTF correspond ainsi à un jeu d'images où chaque image est associée à un point de vue et à une direction de la lumière. Ce procédé de capture permet de modéliser à la fois la méso-structure, la micro-structure et toutes les interactions qui existent entre ces deux couches, pour un même matériau. Afin d'assurer une transition douce entre différents points de vue ou directions de la lumière, un échantillonnage fin est nécessaire, c'est-à-dire qu'une BTF correspond à un nombre d'images important.
Lors de la transmission des données correspondant à ces matériaux modélisés, aussi appelés textures ou textures multidimensionnelles, et lors du rendu en temps réel de ces textures, l'information brute véhiculée par les BTF doit donc être exprimée différemment, afin de répondre aux contraintes de rapidité d'accès aux données, et de tailles de mémoire limitées.
D'autres procédés similaires à celui permettant d'obtenir des BTF existent, qui génèrent des textures multidimensionnelles en utilisant des dimensions en moins ou en plus par rapport aux BTF. Ainsi les "Polynomial Texture Map (PTM)" sont des textures où seule la direction de la lumière fait varier l'aspect de la surface associée. De même les "Time-Varying BTF" sont des BTF auxquelles une dimension est ajoutée, permettant de faire varier l'aspect d'une surface avec le temps. Ces textures sont elles aussi représentées par un nombre très important de données qui nécessitent un codage approprié.
Les techniques de codage existantes permettant de compresser les données de ces textures multidimensionnelles évoluent essentiellement suivant deux approches.
La première approche consiste à approximer une texture multidimensionnelle par des modèles de fonctions continues. Par exemple une texture exprimée sous la forme d'une BTF est approximée par des modèles de fonctions BRDF, ou par des polynômes bi-quadratiques. En effet cette BTF étant exprimée par un ensemble d'images, chacune étant la photographie de la surface d'un matériau correspondant à la texture selon un point de vue et une direction de la lumière donnés, en classant différemment ces données on obtient pour chaque pixel sa variation en fonction de la direction de la lumière considérée et en fonction du point de vue considéré. Autrement dit cette BTF est approximée par un ensemble de modèles de fonctions BRDF:
BTF(z,v,l) ≈ {BRDFz (v,l)},\/z où
- z est la projection des coordonnées spatiales x et y définissant initialement un pixel dans la BTF, sur une seule dimension, - v est la projection des coordonnées polaires initiales θv et φv définissant initialement la direction d'un point de vue dans la BTF, sur une seule dimension,
- / est la projection des coordonnées polaires initiales θ, et φ, définissant initialement une direction de la lumière dans la BTF, sur une seule dimension,
- et BRDFz(v, I) est un modèle de fonction BRDF pour le pixel z, dans lequel la direction de la lumière et la direction d'un point de vue sont exprimées chacune sur une seule dimension. De telles méthodes d'approximation par des modèles de fonctions BRDF sont décrites notamment dans les articles suivants:
- "Réflectance field based real-time, high-quality rendering of bidirectional texture functions", de J. Meseth, G. Mϋller et R. Klein, publié en février 2004 dans le journal "Computers and Graphics", - "Efficient rendering of spatial bi-directional réflectance distribution functions", de D.K. McAllister, A. Lastra et W. Heidrich, publié à l'occasion d'une conférence "ACM SIGGRAPH/EUROGRAPHICS conférence on Graphics Hardware" de 2002,
- et "Non-linear réflectance model for bidirectional texture function synthesis", de J. Filip et M. Haindl, publié en 2004 à l'occasion d'une conférence "International Conférence on Pattern Récognition (ICPR)". Le modèle de fonction BRDF utilisé pour cette approximation est par exemple celui de E. P. F. Lafortune, S-C. Foo, K.E. Torrance et D.P. Greenberg décrit dans leur article "Non-linear approximation of réflectance functions" publié à l'occasion d'une conférence "ACM SIGGRAPH" de 1997.
De façon similaire, une BTF est parfois approximée par des polynômes bi-quadratiques:
BTF(z,v,θι,φι) ≈ {Pv{z,θι,φι)}yv où - z est la projection des coordonnées spatiales x et y définissant un pixel initialement dans la BTF, sur une seule dimension,
- v est la projection des coordonnées polaires θv et φv définissant initialement la direction d'un point de vue dans la BTF, sur une seule dimension,
- et Px, (z, θ,, φt) est un polynôme bi-quadratique d'approximation de la
BTF pour un point de vue donné.
Les méthodes basées approximation selon cette première approche permettent d'obtenir une représentation compacte et continue des textures, qui s'adapte bien aux algorithmes de rendu actuel, effectués en général directement sur des cartes graphiques programmables. Elles sont toutefois limitées par la complexité des calculs nécessaires. En effet, si une décomposition en valeur singulière d'une BTF suffit pour obtenir une approximation par des polynômes bi-quadratiques, l'approximation de la même fonction par des modèles de fonctions BRDF s'avère souvent de résolution très complexe. De plus, ces approximations ne permettent pas de rendre la variété des effets capturés lors de l'acquisition des BTF. Les effets liés aux déplacements du point de vue ou de la direction de la lumière nécessiteraient, pour être pris en compte, l'utilisation de modèles de fonctions BRDF encore plus complexes, ou de polynômes différents, tels que décrits dans les articles:
- "A réflectance model for computer graphies", de R.L. Cook et K.E. Torrance, publié en 1982 dans le magazine "ACM Transactions On Graphics", - ou "Measuring and modeling anisotropic reflection", de GJ. Ward, publié à l'occasion d'une conférence "ACM SIGGRAPH" de 1992. De plus les spéculantes et singularités, telles que des occlusions ou des ombrages, induites par la méso-structure des surfaces modélisées, sont évincées par ces méthodes basées approximation. La seconde approche consiste à effectuer une décomposition en base linéaire d'une texture multidimensionnelle. Etant donnée une texture, exprimée par exemple sous la forme d'une BTF, cette BTF étant assimilable à un signal multidimensionnel, une analyse en composantes principales, ou décomposition en valeurs singulières, est appliquée. Cette méthode consiste à rechercher les directions dans l'espace qui représentent le mieux les corrélations du jeu de données constitué par la BTF. Une nouvelle base est alors définie, résultante de l'orthogonalisation du domaine d'analyse par une recherche des vecteurs propres et valeurs propres de la matrice de covariance associée à la BTF. Les axes du nouveau repère associé sont tels que la variance des échantillons initiaux de la BTF est maximale. Les vecteurs propres sont ensuite triés par ordre d'importance, en fonction de leurs valeurs propres correspondantes, par ordre décroissant. On garde ainsi uniquement les axes les plus influents. Les données initiales de la BTF sont ensuite projetées dans ce nouvel espace de dimensions réduites. On obtient donc, par combinaison linéaire, une approximation du signal original dans cette nouvelle base :
BTF{x,y,θv,φv,θι,φι) ≈ Yjgt{x,y) -hι{θv,φv,θι,φ1) où les fonctions g, représentent les poids issus de la projection dans la nouvelle base {h, } , composée de c vecteurs issus de la réduction de dimensionnalité.
Les méthodes existantes selon cette deuxième approche diffèrent par le choix des données à analyser ou sur l'organisation de la décomposition.
Ainsi, certaines méthodes utilisent l'ensemble des données de la BTF comme espace d'analyse, comme pour l'équation ci-dessus et comme décrit dans l'article de M. L. Koudelka, S. Magda, P.N. Belhumeu, et DJ. Kriegman, intitulé "Acquisition, compression and synthesis of bidirectional texture functions" et publié à l'occasion d'un atelier international "Texture Analysis and Synthesis" de 2003. D'autres méthodes utilisent une représentation par point de vue afin d'exploiter la cohérence lors d'un changement de direction de la lumière, plus forte que lors d'un changement de point de vue:
BTF (z, v,l) = {BTFv (z, l)}yv
avec BTFv(z,l) ≈ ∑gvAl) 'hVJ (z) ,
où les fonctions gv ι représentent les poids issus de la projection dans une nouvelle base |ΛV }, d'un échantillon BTFv(z,l) correspondant aux données de la BTF BTF(z, v, I) pour un point de vue donné v . Ces méthodes de représentation par point de vue sont décrites dans les articles: - "Efficient and realistic visualization of cloth", de M. Sattler, R. Sarlette et
R. Klein, publié à l'occasion d'une conférence internationale "Eurographics Symposium on Rendering " de 2003, - et "Preserving realism in real-time rendering of bidirectional texture functions", de J. Meseth, G. Mϋller et R. Klein, publié à l'occasion d'une conférence internationale "OpenSG Symposium" de 2003.
Les mêmes auteurs, G. Mϋller, J. Meseth et R. Klein, dans leurs articles
"Compression and real-time rendering of measured BTFs using local Principal
Component Analysis (PCA)", présenté à l'atelier international "Vision,
Modeling and Visualisation" de 2003, et " Fast environmental lighting for local- PCA encoded BTFs", publié à l'occasion de la conférence internationale
"Computer Graphics International (CGI)" de 2004, proposent une représentation par bloc des textures multidimensionnelles en regroupant par paquets les données ayant le plus de vraisemblance. L'analyse est ensuite effectuée sur chaque bloc individuellement et l'approximation analytique de la BTF associée est :
5rF(z,v,/) ≈f (=l>,ω>)Aω>,0 où les fonctions gk(z),, représentent les poids issus de la projection dans de nouvelles bases de la BTF 57F(z,v,0dans laquelle les données ont été regroupées par blocs en fonction des pixels les plus corrélés, k(z) étant une fonction correspondant à une table de correspondance associant un pixel à un bloc de vraisemblance.
Toujours selon cette deuxième approche, une méthode multi-résolution est proposée par W. -C. Ma, S.-H. Chao, Y.-T. Tseng, Y.-Y. Chuang, C- F.Chang, B.-Y. Chen et M. Ouhyoung, dans leur article HLevel-of-detail représentation of bidirectional texture functions for real-time rendering", publié en 2005 à l'occasion d'une conférence internationale "Symposium on Interactive 3D graphies and games". Ils réalisent tout d'abord une transformation du domaine initial en pyramide de Laplace pour chaque pixel. Cette pyramide, constituée de plusieurs niveaux, est construite en filtrant le niveau de détail le plus élevé pour obtenir une représentation de plus basse résolution. Les coefficients de la pyramide sont par la suite décomposés par une analyse en composantes principales.
Enfin M.A.O. Vasilescu et D. Terzopoulos, dans leur article "Tensortextures: multilinear image-based rendering", publié en 2004 dans le journal "ACM Transactions On Graphics", proposent une méthode multilinéaire: ils décomposent la BTF en produit de tenseurs. Chaque tenseur représente deux dimensions de la BTF :
- un tenseur spatial représente la projection des coordonnées spatiales JC et y sur une seule dimension,
- un tenseur lié au point de vue représente la projection des coordonnées polaires θv et φv sur une seule dimension,
- et un tenseur lié à la direction de la lumière représente la projection des coordonnées polaires θ, et φ, , sur une seule dimension.
Ces tenseurs sont calculés grâce à une décomposition en valeurs singulières en trois dimensions, chaque dimension représentant un doublet comme énoncé précédemment. Cette méthode permet donc une réduction de dimension plus fine dans la mesure où elle permet de privilégier une dimension, c'est-à-dire un tenseur, individuellement. La décimation n'est donc pas totalement aléatoire sur l'ensemble de la BTF car l'erreur d'approximation peut être ciblée en fonction du nombre de composantes principales retenues pour chaque dimension.
Les méthodes basées décomposition selon cette deuxième approche améliorent les résultats qualitatifs par rapport aux méthodes basées approximation, le choix du nombre de composantes principales déterminant la qualité des textures compressées par de telles méthodes. Elles définissent de plus une représentation compacte et discrète des textures multidimensionnelles. Cette compacité est due au fait que les vecteurs issus de la décomposition sont classés par ordre d'importance et seuls les vecteurs les plus représentatifs sont pris en compte. Cependant cette décimation est aléatoire et ne permet pas de définir quels détails seront occultés lors de la transformation. Elle évince de plus certaines singularités capturées lors du processus d'acquisition, les axes substitués correspondant à des zones de faible corrélation. Ce manque d'information fréquentielle limite la flexibilité de ces méthodes: elles ne permettent pas de fournir directement une représentation suivant différents niveaux de détails, par un décodage progressif de l'information. Une représentation multi-résolution des textures compressées par ces méthodes nécessite, comme dans l'article "Level-of- detail représentation of bidirectional texture functions for real-time rendering", des transformations supplémentaires.
Il est d'ailleurs à noter que la méthode multi-résolution basée décomposition mentionnée dans cet article produit en fait une représentation de texture par résolution et ne correspond donc pas à une unique représentation multi-résolution permettant un décodage progressif de l'information en fonction d'un choix de résolution.
De plus, ces méthodes fournissant une représentation discrète, elles nécessitent, lorsqu'un niveau de détail élevé est nécessaire sur une zone d'une texture lors de son rendu, une interpolation sur l'ensemble des dimensions de cette texture à l'aide d'échantillons voisins issus du processus d'acquisition.
Les méthodes existantes de compression de texture ne permettent donc pas de conserver l'ensemble des détails capturés d'une texture, ni de fournir un décodage progressif de l'information de texture afin de s'adapter aux contraintes matérielles lors de la transmission de cette information, liées par exemple à la puissance des cartes graphiques des récepteurs ou au débit du réseau utilisé. Cette faculté est cependant nécessaire pour généraliser l'utilisation des textures aux systèmes décentralisés ou à une plus grande gamme de périphériques, comme les terminaux mobiles.
La présente invention a pour but de résoudre les inconvénients de la technique antérieure en fournissant notamment un procédé et un dispositif de codage de données représentatives d'une texture multidimensionnelle, utilisant les propriétés de l'analyse en ondelettes sur toutes les dimensions de cette texture.
A cette fin, l'invention propose un procédé de codage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte les étapes de:
- analyse en ondelettes desdites données sur lesdites dimensions,
- et compression de données obtenues à partir du résultat de ladite analyse.
Grâce à l'invention, on obtient une représentation de texture multidimensionnelle efficacement compressée: le taux de compression obtenu est meilleur que dans l'art antérieur, tout en gardant un bon niveau de détail et en ne nécessitant qu'une faible complexité de calcul, ce qui permet de reconstruire en temps réel les données initiales lors du rendu. En effet, bien que l'algèbre multilinéaire s'avère parfois coûteux lors de la synthèse c'est-à- dire lors du décodage, les tenseurs utilisés dans l'invention sont creux, c'est-à- dire que la plupart de leurs coefficients sont nuls, ce qui, dans la pratique, implique peu de calculs.
Le fort taux de compression obtenu par le procédé de codage selon l'invention permet de conserver une représentation de texture de très bonne qualité, qui conserve notamment tous les effets liés au déplacement du point de vue ou de la direction de la lumière.
Ces avantages sont liés aux propriétés de l'analyse en ondelettes, qui exploite la corrélation dimensionnelle et inter-dimensionnelle sans transformation préalable. De plus l'analyse en ondelettes correspond à une analyse fréquentielle d'un signal initial, qui est décomposé en bandes de fréquences. De ce fait, il est possible de cibler la décimation de manière fréquentielle et cela pour chaque dimension du signal. Cela permet de conserver toutes les singularités de la texture compressée selon l'invention. Cette analyse est en outre une analyse multi-résolution, elle produit une représentation du signal initial par échelle, dans laquelle on qualifie de niveau le plus grossier les coefficients basse-fréquence et de niveau le plus fin la reconstruction à partir des coefficients haute-fréquence. Cette caractéristique permet de définir différents niveaux de détails à partir d'une même représentation de texture. Elle permet également de représenter l'information de texture de manière progressive: dans une telle représentation, les données sont organisées par ordre d'importance, les coefficients minimisant l'erreur de reconstruction étant placés au début. Le principe de cette représentation consiste à ajouter des détails à l'approximation du signal d'origine. Ainsi, si la transmission sur un réseau ou vers un processeur de données de texture codées selon l'invention est interrompue, par exemple pour respecter certains critères tels que la taille des données reçues, l'information déjà transmise sera exploitable. Un autre avantage de cette représentation progressive est l'adaptation possible des données de texture codées selon l'invention à différents types de périphériques graphiques, n'ayant pas les mêmes capacités en termes de calcul et de taille de mémoire, tels que des centres de réalité virtuelle, des ordinateurs de bureau ou des périphériques mobiles. Cette représentation progressive permet également l'adaptation des données au débit de transmission lors d'une application décentralisée.
Un autre avantage lié à l'analyse par ondelettes est de rendre le codage selon l'invention extrêmement configurable: suivant que l'on privilégie une représentation de la meilleure qualité possible ou une représentation la plus compacte possible, on choisit une compression sans pertes ou une compression avec pertes.
Il est en outre possible d'effectuer le codage selon l'invention sur des dispositifs ou systèmes à architecture parallèle, tels que les processeurs graphiques actuels appelés GPU, d'après l'anglais "Graphics Processing Unit", des processeurs multi-cœur ou une grappe d'ordinateurs personnels. Ii est à noter que de par ses avantages liés aux possibilités de représentation progressive des données de texture, et de parallélisme des calculs, le procédé de codage selon l'invention est compatible avec les systèmes de navigation virtuelle "peer-to-peer", qui nécessitent une résistance aux pannes et une grande flexibilité de transmission de l'information. Il permet notamment de transmettre en parallèle des données de texture depuis différents émetteurs, vers des récepteurs de capacités très différentes.
Enfin, le procédé de codage selon l'invention autorise un accès dynamique et rapide aux données de texture codées selon l'invention. En effet, il n'est pas nécessaire de reconstruire l'ensemble des données initiales à chaque nouvelle image d'une même texture lors de son rendu, car le codage des données selon l'invention permet une reconstruction locale de zones d'intérêt.
Selon une caractéristique préférée, le procédé de codage selon l'invention comporte une étape préalable de réorganisation desdites données représentatives d'une texture multidimensionnelle selon un nombre de dimensions prédéterminé. Cette étape de réorganisation des données de texture permet de simplifier la décomposition en ondelettes, par réduction du nombre de dimensions notamment.
Selon une autre caractéristique préférée, dans ladite étape de réorganisation lesdites données sont rangées de manière à maximiser la corrélation entre deux échantillons successifs desdites données selon au moins une dimension.
Le fait de maximiser la corrélation entre échantillons avant la décomposition en ondelettes améliore la compression des données lors de leur codage.
Selon une autre caractéristique préférée, lesdites données représentatives d'une texture multidimensionnelle représentent des couleurs selon le système de codage couleur YUV.
L'utilisation du système de codage couleur YUV au lieu d'un système de codage classique Rouge/Vert/Bleu RVB, pour représenter les couleurs de la texture codée selon l'invention, permet d'obtenir, pour une qualité visuelle équivalente, de meilleurs taux de compression. En effet, l'œil humain étant moins sensible aux variations chromatiques et plus à la luminance, ce choix permet lors de l'étape de quantification associée au codage, de coder moins précisément les paramètres U et V représentatifs de la chromaticité, que le paramètre Y représentatif de la luminance.
Selon une autre caractéristique préférée, l'étape de compression du procédé de codage selon l'invention utilise un codage de type "zerotree".
Ce type de codage permet d'optimiser la compression des données de texture ayant été analysées en ondelettes.
L'invention concerne aussi un procédé de décodage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte les étapes de: - décompression desdites données, - et synthèse en ondelettes sur lesdites dimensions de données obtenues à partir de ladite décompression.
L'invention concerne aussi un signal représentatif d'une texture multidimensionnelle initialement représentée par des données organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce que lesdites données ont été codées par analyse en ondelettes sur lesdites dimensions, puis par compression de données obtenues à partir du résultat de ladite analyse. L'invention concerne encore un dispositif de codage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte: - des moyens d'analyse en ondelettes desdites données sur lesdites dimensions,
- et des moyens de compression de données obtenues à partir desdits moyens d'analyse.
L'invention concerne également un dispositif de décodage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte:
- des moyens de décompression desdites données, - et des moyens de synthèse en ondelettes sur lesdites dimensions de données obtenues à partir desdits moyens de décompression. Le procédé de décodage, le signal, le dispositif de codage et le dispositif de décodage présentent des avantages analogues à ceux du procédé de codage selon l'invention. 1 0
L'invention concerne enfin un programme d'ordinateur comportant des instructions pour mettre en œuvre le procédé de codage selon l'invention ou le procédé de décodage selon l'invention, lorsqu'il est exécuté sur un ordinateur.
D'autres caractéristiques et avantages apparaîtront à la lecture d'un mode de réalisation préféré décrit en référence aux figures dans lesquelles :
- la figure 1 représente l'échantillonnage de l'acquisition d'une BTF modélisant une texture,
- la figure 2 est un tableau illustrant les valeurs de cet échantillonnage, - la figure 3 représente une interprétation de cette BTF,
- la figure 4 représente un mode de réalisation du procédé de codage et du procédé de décodage selon l'invention,
- la figure 5 représente des étapes du procédé de codage selon l'invention, tel que décrit dans ce mode de réalisation, - la figure 6 représente un niveau de décomposition en ondelettes de données de texture,
- la figure 7 représente une décomposition en ondelettes de données de texture,
- la figure 8 représente un arbre de décomposition en paquets d'ondelettes de données de texture,
- la figure 9 représente l'attribution de coûts aux éléments de cette décomposition en paquets d'ondelettes,
- la figure 10 représente un autre arbre de décomposition en paquets d'ondelettes de données de texture, - la figure 11 représente un format de représentation de données de texture codées selon l'invention,
- la figure 12 représente des étapes du procédé de décodage selon l'invention tel que décrit dans ce mode de réalisation. Selon un mode préféré de réalisation de l'invention, on utilise le procédé de codage selon l'invention pour compresser une texture multidimensionnelle exprimée sous la forme d'une BTF en six dimensions. Cependant, la décomposition en ondelettes étant généralisable à un nombre quelconque de dimensions, le procédé selon l'invention est également applicable aux textures multidimensionnelles représentées différemment, par exemple sous forme de "Polynomial Texture Map" en quatre dimensions ou de "Time-varying BTF" en sept dimensions.
La BTF exprimant cette texture est le fruit d'un processus d'acquisition représenté à la figure 1. La BTF est échantillonnée selon un hémisphère de prises de vue. Dans le repère orthonormal d'origine O et d'axes X, Y et Z, chaque point de la texture est ainsi photographié sous une direction de point de vue de coordonnées polaires θv et φv, et selon une direction de la lumière de coordonnées polaires θι et φι.
Le tableau TAB de la figure 2 indique le nombre de photographies prises pour une latitude θv ou θι donnée. Ainsi pour une latitude θv égale à 15 degrés, l'angle φv varie de 72 degrés en 72 degrés, ce qui correspond à 5 photographies prises pour cette latitude. En sommant les valeurs du nombre d'échantillons sur la première colonne, il y a donc 80 valeurs de directions de point de vue et 80 valeurs de directions de la lumière utilisées pour l'échantillonnage, ce qui produit une BTF constituée de 6400 images.
La figure 3 illustre cette interprétation de la BTF: chacune des images I de ces 6400 images représente la texture en coordonnées paramétriques x et y, et correspond à une direction de point de vue (θVl φv) et une direction de la lumière (θι, q>ι).
Il est à noter que des données similaires de BTF sont téléchargeables sur le site de l'université de Bonn à l'adresse internet http://btf.cs.uni- bonn.de/., le mode d'acquisition de ces données étant plus amplement détaillé dans l'article de G. Mϋller, G. H. Bendels et R. Klein intitulé "Rapid synchronous acquisition of geometry and BTF for cultural héritage artefacts", publié en novembre 2005 à l'occasion d'une conférence "6th International Symposium on Virtual Reality, Archaeology and Cultural Héritage (VAST)".
De plus, l'échantillonnage n'étant pas régulier et possédant des zones frontières, le procédé de codage selon l'invention utilise des ondelettes qui sont évidemment des ondelettes de type "seconde génération", car les ondelettes de première génération ne sont pas adaptées à ce type d'échantillonnage.
Les images I formant les données de la BTF sont stockées dans une base de données BDD représentée à la figure 4, le procédé de codage selon l'invention étant implémenté dans ce mode de réalisation de manière logicielle dans un ordinateur ORD ayant accès à cette base de données. Les calculs nécessaires au procédé de codage selon l'invention sont effectués dans le processeur CPU de l'ordinateur ORD. En variante, étant donnée l'importance de la taille des données sur lesquelles sont effectués les calculs nécessaires à leur codage, ces calculs sont effectués sur plusieurs ordinateurs fonctionnant en parallèle.
En référence à la figure 5, le procédé de codage selon l'invention est représenté sous la forme d'un algorithme comportant des étapes C1 à C3.
La première étape C1 est une réorganisation des données de la BTF dont les données sont initialement organisées suivant six dimensions, en un nombre de dimensions réduit, de manière à limiter la complexité des calculs.
Le choix de ce nombre de dimensions dépend des applications utilisant les données compressées, suivant que l'on privilégie des calculs moins complexes ou un taux de compression plus important. En effet plus on garde de dimensions plus on exploite la cohérence inter-dimensionnelle et plus le 1 es
taux de compression est important. Dans ce mode de réalisation, on choisit une réorganisation des données de la BTF en quatre dimensions, compromis entre rapidité et compression:
BTF(x, y, θv , φv , θ, , φ, ) = BTF(x, y, v, /) , où
- v est la projection des coordonnées polaires initiales θv et φv définissant initialement la direction d'un point de vue dans la BTF, sur une seule dimension,
- et / est la projection des coordonnées polaires initiales θ, et φt définissant initialement une direction de la lumière dans la BTF, sur une seule dimension.
En variante, les données de la BTF ne sont pas réorganisées, l'analyse en ondelettes se faisant alors sur six dimensions. Dans cette variante, on utilise par exemple deux types d'ondelettes: - des ondelettes en deux dimensions non-séparables afin d'adapter les filtres d'analyse à l'échantillonnage de la BTF suivant les directions de point de vue et de la lumière, - et des ondelettes en une dimension séparables pour l'analyse spatiale. Dans une autre variante de réalisation, les données initiales de la BTF sont réorganisées suivant trois dimensions suivant une décomposition appelée "réflectance field", c'est-à-dire qu'elle est exprimée par point de vue v et que la direction de la lumière est projetée sur une seule dimension:
BTF(x,y,θv,φv,θι,φ,) = {BTFv(x,yJ)},Vv Dans une autre variante de réalisation, les données de la BTF sont réorganisées suivant cinq dimensions, la direction de la lumière étant projetée sur une seule dimension:
BTF(x,y,θv,φv,θι,φι) =BTF(x,y,θv,φv,l)
Cette dernière variante est intéressante par exemple lorsqu'on échantillonne plus la direction du point de vue que la direction de la lumière. 1 Q
Lors de cette étape C1 de réorganisation des données de la BTF, la projection v correspondant au doublet (θv ,φv ) est classée par ordre croissant suivant θv et φv , c'est-à-dire que selon la dimension du point de vue v les images I sont classées dans l'ordre d'échantillonnage suivant: (0,0), (15,0),(15,72)I..., (75,345). De même la projection / correspondant au doublet (θ, ,φt ) est classée par ordre croissant suivant θ, et φ, .
En variante, les images I sont classées de manière à maximiser la corrélation entre deux images successives selon la direction de la lumière. Ce classement s'effectue par exemple de la manière suivante sur l'ensemble des images ayant en commun une même direction de point de vue:
- on choisit une image racine dans cet ensemble, par exemple l'image de projection / correspondant au doublet (0,0) en coordonnées polaires,
- on recherche ensuite itérativement l'image suivante à partir de l'image précédente, cette image correspondant à l'image minimisant la différence entre l'image précédente et l'ensemble des images non déjà classées.
Ce classement des images I par ordre de vraisemblance suivant l'axe correspondant à la projection /, permet dans la suite d'améliorer la compression lors de l'étape C3.
Il est de plus à noter que les données de la BTF sont codées à l'acquisition au format RVB. Or ce format de codage couleur ne permet pas d'exploiter le facteur perception à son maximum. En effet, l'œil humain étant particulièrement sensible au changement de luminance, on réalise de préférence dans cette étape C1 un changement d'espace de couleur RVB vers l'espace couleur YUV, où Y représente la luminance, et U et V la chrominance. Ce changement a un impact sur la suite du traitement car l'utilité d'une telle modification est de fournir une quantité d'information plus importante pour la luminance par rapport à la chrominance lors de la quantification à l'étape C3. 2
La seconde étape C2 du procédé de codage est l'analyse en ondelettes des données ainsi réorganisées et reformatées, sur les quatre dimensions choisies à l'étape C1.
Il est à noter que l'expression "analyse en ondelettes" signifie que l'on décompose un signal en ondelettes ou en paquets d'ondelettes, par transformées successives en ondelettes. Une analyse en ondelettes recouvre donc au moins une décomposition en ondelettes.
Cette décomposition en ondelettes se fait suivant l'organisation choisie à l'étape C1. Comme indiqué plus haut, l'utilisation d'ondelettes de seconde génération est nécessaire du fait de l'irrégularité des intervalles d'échantillonnage et des zones frontières. Il est de plus à noter que même à supposer que l'on synthétise de nouveaux échantillons à l'étape C1 afin de régulariser ces intervalles, le domaine d'analyse restant toujours borné, les ondelettes de seconde génération restent nécessaires. Par simplicité dans ce mode de réalisation, on utilise une transformée en ondelettes simple de type "Unbalanced Haar Transform", d'ordre 1 , utilisant des ondelettes de seconde génération orthogonales, faciles à construire grâce à la méthode du "lifting scheme". Cette construction est détaillée dans un cours de W. Sweldens and P. Schrôder, intitulé "Building your own wavelets at home" et publié en 1996 par ACM SIGGRAPH dans "Wavelets in Computer Graphics". Ces ondelettes étant séparables, la décomposition est effectuée dimension par dimension ce qui permet de rester indépendant de l'organisation des données choisies à l'étape C1. De plus, en utilisant la base d'ondelettes de Haar, aucune adaptation aux frontières n'est nécessaire car la décomposition s'effectue sur deux échantillons successifs, autrement dit le calcul de la décomposition près des frontières ne nécessite pas l'ajout d'échantillons fictifs. Enfin, afin de simplifier cette décomposition et du fait de la réorganisation des données en quatre dimensions à l'étape C1 , on se permet de considérer dans cette étape C2 que les intervalles d'échantillonnage sont réguliers. En variante, si les données de la BTF ont été réorganisées à l'étape C1 suivant un nombre de dimensions supérieur à quatre, on pondère les calculs lors de la décomposition en ondelettes afin de transformer un intervalle irrégulier en intervalle régulier et se ramener au cas de figure régulier. Cette pondération permet de rendre la décomposition en ondelettes plus fidèle à la réalité, c'est-à-dire que lors de la décompression les données décompressées permettent de synthétiser de nouvelles vues de texture très réalistes.
En variante, on utilise dans cette décomposition des ondelettes de base plus complexe, d'ordre supérieur. Cela permet, au prix cependant de calculs plus complexes et plus longs, de conserver malgré la compression une représentation de texture de très bonne résolution. On utilise par exemple des ondelettes bi-orthogonales, pratiques pour leur facilité de construction via la méthode du "lifting scheme", ou des ondelettes géométriques en considérant la configuration spatiale de la texture comme une géométrie dans un espace de même dimension. Par exemple, sur des données réorganisées à l'étape C1 sur trois dimensions, on utilise des ondelettes basées maillage utilisant comme primitive le quadrilatère, et en appliquant des techniques de subdivision classique telles que la technique "Butterfly". De manière générale, l'utilisation de base d'ondelettes ayant deux moments nuls est un bon compromis pour concilier qualité de restitution et vitesse de calcul.
Plus précisément, dans la variante principale de réalisation du procédé de codage selon l'invention, la décomposition en ondelettes à l'étape C2 se fait à chaque niveau j de décomposition selon le schéma de la figure 6. Soit SJ le signal formé de l'ensemble des données {s^J,mn } du j-ième niveau de décomposition en ondelettes dans la base de Haar, des données réorganisées obtenues à la fin de l'étape C1 , et dans lequel:
- k est un indice représentant la k-ième valeur du signal selon l'axe de la coordonnée spatiale x , - p est un indice représentant la p-ième valeur du signal selon l'axe de la coordonnée spatiale y ,
- m est un indice représentant la m-ième valeur du signal selon l'axe de la projection / , - et n est un indice représentant la n-ième valeur du signal selon l'axe de la projection v .
La décomposition se fait dimension par dimension, par bloc de données correspondant chacun à l'ensemble des valeurs de la BTF selon une dimension, lorsqu'on fixe chacune des trois autres dimensions à une valeur donnée. L'ordre de traitement de ces dimensions est choisi en fonction de la corrélation des données de la BTF. La corrélation spatiale de la texture étant plus forte que sa corrélation lors d'un changement de direction de la lumière, elle même plus forte que lors d'un changement de direction de point de vue, on effectue la décomposition en ondelettes d'abord suivant l'indice k, puis suivant l'indice p, puis suivant l'indice m et enfin suivant l'indice n.
Ainsi lors de sa décomposition en ondelettes, le signal SJ est soumis d'abord suivant l'axe de la coordonnée spatiale x , aux fonctions suivantes:
- l'opérateur s dit "split" sépare les données d'indice pair et les données d'indice impair dans la direction considérée, donc ici suivant l'indice k: j ' où k' est un indice entier défini par: k = 2k' lorsque k est pair et k ≈ 2k'+l lorsque k est impair,
- le filtre passe-bas h effectue les moyennes des données {sk J pmn } suivant la direction considérée, ce qui produit les données {s^J pmn } définies par:
CJ , OJ ç,jh _ °(2k')pmn "*" {2k'+\)pmπ ^k'pnw ~ Z ' - et le filtre passe-haut g calcule les différences entre les données {s^mM } suivant la direction considérée, ce qui produit les données définies par:
J lS _ CJ _ CJ
" k'pmn ~~ Lj{2k'+l)pmn iJ(2k')pmn •
5 En réalité la décomposition s'effectue suivant la méthode du "lifting scheme", ce qui signifie pour la décomposition dans la base de Haar que l'on calcule d'abord la différence entre deux valeurs du signal SJ puis on calcule la somme de ces deux valeurs à partir de cette différence:
i n A ιg — vj )pmn _ ÇJ
I KJ " k'pmn ~ ° '(2k '+l °(2k')pmn <
J JS nι ιi<s Vjh - <ZJ | k'P"m
PUIS ^ k'pmn ~ ^(2k')pm« + Z '
Cela permet au processeur CPU de stocker la valeur de dk Jfpmn à l'endroit de la valeur de S(2k,+i)pmn , puis de stocker la valeur de Sk Jh pmn à l'endroit de la valeur de S(lk,)pmn . Cela permet de sauver de la place mémoire au niveau du
15 processeur CPU. De plus le caractère local de la décomposition en ondelettes, ici sur deux échantillons successifs, permet à la décomposition d'être effectuée de manière "out of core", c'est-à-dire que l'ensemble des données à traiter n'est pas entièrement contenu dans la mémoire principale. Ce caractère permet également aux données d'être traitées en parallèle par 0 plusieurs processeurs. En outre, contrairement aux méthodes de l'art antérieur, le domaine d'analyse n'a pas besoin d'être segmenté pour être traité dans son entier.
Les données ) sont ensuite soumises aux mêmes fonctions mais suivant l'indice p: 5 - l'opérateur s sépare les données {sk J!p'mn } et les données [dk J?pnm } suivant leurs indices pairs ou impairs, - le filtre h produit à partir des données {sk'pmn} les données {sk J',p.mn} et à partir des données {dk Jfpmπ } les données {dk Jfp',mn },
- et le filtre g produit à partir des données \s^J pmn } les données ψ£ξ<mn } et à partir des données les données où p' est un indice entier défini par: p = 2p' lorsque p est pair , et p = 2p'+l lorsque p est impair.
Puis l'ensemble des données {s#J, bfiJ.fa$J. et ^J obtenues sont à nouveau soumises aux mêmes fonctions, mais suivant l'indice m. Ainsi si l'on décrit seulement la décomposition des données
Ptyoui j '
- l'opérateur s sépare ces données suivant leurs indices pairs ou impairs: ) ' où m' est un indice entier défini par: m = 2m' lorsque m est pair , et m = 2m'+l lorsque m est impair,
- le filtre h produit à partir des données {sk Jh p,mn}, les données {sk J!p" !m' , „} définies par: - et le filtre g produit à partir des données définies par: fjjhltg _ ςβh _ ςrjhh
"k'p'm n ~ °ty(2oi'+l>i -
Enfin l'ensemble des données ainsi obtenues par décomposition selon l'indice m sont décomposées suivant l'indice n. Si l'on décrit seulement la décomposition des données {sk J p' h m.n }: - l'opérateur s sépare les données d'indice pair et les données d'indice impair:
I ς jhhh \ _ lςjlιhh ςjhhh \
où «' est un indice entier défini par: n = 2n' lorsque n est pair et n = 2n'+l lorsque n est impair,
- le filtre h effectue les moyennes des données \Sk J ym' ,n} suivant l'indice n, ce qui produit les données {s/y**Λ.} définies par: ojhhh , Qjhhh ςjhhhh _ °k'p:mX2n') "*" J*',pW(2fl'+1) ^k'p'm'n' ~ j <
- et le filtre g calcule les différences entre les données {s^,.} suivant l'indice n, ce qui produit les données définies par:
7 jhhhg o jhhh rr jhhh ak'p'm'ri ~ °4>'m'(2n'+l) ~ °tym'(2n') •
L'ensemble des données produites lors de cette dernière décomposition suivant l'indice n forme le résultat de la décomposition en ondelettes du signal SJ , soit les données du j moins unième niveau de décomposition en ondelettes des données obtenues à la fin de l'étape C1. On distingue dans ce résultat les données basse fréquence de basse résolution, et les autres données qui forment un signal dJ~ι de plus haute fréquence.
Dans une variante de réalisation, la décomposition détaillée ci-dessus est une décomposition en ondelettes classique du signal initial SJ formé des données obtenues à l'étape C1. Dans cette décomposition représentée à la figure 7, seul le signal de basse fréquence SJ~ι est re-décomposé au prochain niveau de décomposition, le signal de détail dJ~ι étant conservé. Ainsi au J moins unième niveau de décomposition, le signal SJ "x est décomposé en ondelettes et produit un signal SJ~2 de plus basse fréquence que le signal SJ ' , et un signal dJ~2 de plus basse fréquence que le signal dJ~\ puis au niveau de décomposition suivant le signal SJ~2 est lui-même décomposé en ondelettes et ainsi de suite. La dernière décomposition en ondelettes sur le signal S1 produit les signaux d° et S0. Les données obtenues à la fin de l'étape C1 étant les images I codées suivant le format YUV et classées suivant 80 directions de point de vue et 80 directions de la lumière, en supposant que ces images sont de résolution 256*256, on s'arrête par exemple au bout de trois niveaux de décomposition en ondelettes. Le résultat de l'analyse en ondelettes est alors formé des signaux S0 , et d° à dJ~\ où J vaut trois. Le signal 5° de basse fréquence contient 10*10*32*32 couleurs codées dans l'espace couleur YUV.
Dans la variante principale de réalisation du procédé de codage selon l'invention, afin de coder la texture de manière optimale, on décompose en fait dans cette étape C2 les données obtenues à la fin de l'étape C1 en paquets d'ondelettes. Une telle décomposition permet de décomposer non seulement récursivement les signaux SJ de basse fréquence, mais aussi les signaux dJ de haute fréquence. Cette décomposition est représentée sur l'arbre de la figure 8. La racine de l'arbre correspond au signal SJ initial contenant les données obtenues à la fin de l'étape C1. Le niveau suivant est le résultat d'une itération de transformation en ondelettes, c'est-à-dire le signal SJ~Ï de basse fréquence et le signal dJ'x de haute fréquence. Puis la décomposition récursive de ces signaux complète les niveaux inférieurs de l'arbre. Ainsi la décomposition du signal SJ~X donne deux signaux SJ~2 et dJ~2 , tandis que la décomposition du signal dJ'x donne également deux signaux SύJ \ et d^ .
Cette décomposition en paquets d'ondelettes permet de choisir un arbre de décomposition optimal suivant un critère donné, tel que l'entropie du codage, un seuil prédéterminé, ou la distorsion générée par le codage. Pour cela on attribue une fonction de coût à chaque décomposition en ondelettes, c'est-à- dire à chaque nœud de l'arbre représenté à la figure 8. Cette fonction de coût correspond au critère choisi pour optimiser l'arbre.
Par exemple, si on choisit de privilégier les décompositions par rapport au nombre de valeurs en dessous d'un seuil, la valeur de la fonction coût au nœud de décomposition correspondant au signal SJ vaut:
Avec P(S^n) = 1 si I SU J mn |> t et P(Sh1nJ = 0 sinon, où t correspond à ce seuil.
Puis on compare la somme des coûts des enfants de chaque parent de l'arbre avec le coût de ce parent. Si cette somme est moins élevée que le coût du parent, on garde les décompositions des enfants, sinon s'arrête à la décomposition parentale dans la suite du procédé de codage.
Par exemple sur l'arbre de la figure 9, où l'on a remplacé chaque nœud de la figure 8 par le coût de sa décomposition, la décomposition en paquets d'ondelettes s'arrêtera sur la branche gauche de l'arbre aux signaux SJ~2 et dJ~2 , qui ne seront pas décomposés, car la somme de leurs coûts est supérieure ou égale au coût de leur signal parent SJ~ι .
Dans ce mode de réalisation de l'invention, on choisit d'utiliser un critère d'entropie pour pondérer l'arbre des décompositions: la valeur de la fonction coût au nœud de décomposition correspondant au signal SJ vaut:
Cette fonction coût définit l'entropie de Shannon, qui mesure la quantité d'information, c'est-à-dire de coefficients différents dans une décomposition. Ce critère est utile au procédé de codage selon l'invention car on garde ainsi la décomposition de plus faible coût entropique.
En variante, dans le cas où la BTF codée selon l'invention est initialement exprimée sur des nombres entiers, l'analyse en ondelettes effectuée à cette étape C2 est une décomposition entière en ondelettes ou une décomposition entière en paquets d'ondelettes. Une telle méthode est décrite dans l'article "Réversible image compression via multi-resolution représentation and prédictive coding", de A. Said et W. Pearlman, publié en 1993 à l'occasion d'une conférence internationale "Visual Communications and Image Processing". Cela optimise encore l'analyse en ondelettes en limitant la taille du résultat de cette analyse. En effet, les données issues de l'analyse sont ainsi représentées avec moins de ressources, la taille en octets d'un entier étant inférieure à celle d'un nombre décimal. Il est à noter que toute base d'ondelettes est modifiable pour effectuer une telle décomposition entière. Par exemple, la transformation par rondelette de Haar du signal SJ suivant l'indice k devient :
JiZ _ C J _ CJ uk'lmn ~ °(2k'+\)lmn °(2k')lmn ' dJg puis S 'k*'imn — = O S (L2k',)]blmr,n + "**""
2 où [uj désigne la valeur entière d'une division u par défaut.
Enfin l'étape C3 du procédé de codage selon l'invention est la compression des données obtenues à la fin de l'étape C2, résultat de l'analyse en ondelettes des données de la BTF réorganisées et reformatées à l'étape C1. Dans ce mode de réalisation, cette compression utilise un codage dit
"zerotree", qui exploite la structure arborescente de la décomposition en ondelettes. Cette technique de codage connue de l'Homme du métier est par exemple détaillée dans les articles suivants:
- "An embedded wavelet video coder using three-dimensional set partitioning in hierarchical trees (SPIHT)" de B.-J. Kim et W.A.
Pearlman, publié en 1997 à l'occasion d'une conférence internationale "Data Compression Conférence", 2Q
- et "An embedded hierarchical image coder using zerotrees of wavelet coefficients", de J. M. Shapiro, publié en 1993 à l'occasion d'une autre conférence internationale "Data Compression Conférence". Le principe de cette technique de codage est de considérer que les coefficients basse-résolution contenus dans les signaux SJ sont grands par rapport aux coefficients de détail contenus dans les signaux dJ , et que plus j est petit, plus les coefficients de détail sont grands. Cela permet d'utiliser la dépendance inter-échelles de ces coefficients, c'est-à-dire entre deux niveaux de décomposition, pour effectuer le codage des données. Plus précisément, on lie un coefficient de détail au niveau le plus grossier à un nombre de coefficients situés au niveau supérieur dans une même direction, puis ces coefficients sont à leur tour liés au niveau suivant et ainsi de suite. Ce nombre est égal à une puissance de deux, cette puissance étant égale à la dimension de l'espace d'analyse.
Par exemple, si la décomposition en paquets d'ondelettes retenue est celle présentée sur la figure 10, c'est-à-dire que les données obtenues à la fin de l'étape C2 sont celles des signaux SJ'\ dJ'\ dJ~2 , S^x , dûJ lx et </£?, , un coefficient du signal ύ?J~3 est lié à 16 coefficients du signal dJ~2 . II est à noter que la méthode de codage "zerotree" étant usuellement appliquée aux décompositions en ondelettes, quelques adaptations sont nécessaires pour l'appliquer à une décomposition en paquets d'ondelettes, comme détaillé dans l'article "Adaptive wavelet packet basis sélection for zerotree image coding", de N. Rajpoot, R. Wilson, F. Meyer et R. Coifman, publié en 2003 dans la revue "Institute of Electrical and Electronics Engineers (IEEE) Transactions on image processing".
En effet la hiérarchie au sens du codage « zerotree », n'est plus la même que dans une décomposition classique en ondelettes. Certaines règles pour le rattachement des coefficients d'un niveau à un autre doivent donc être 3Q
ajoutées pour conserver une réelle décroissance des coefficients au fur et à mesure des niveaux de décomposition.
Ainsi sur la figure 10, si le signal dJ~2 avait été re-décomposé sur un dernier niveau J-3, on lierait un coefficient du signal dJ'^ non pas à 16 coefficients du signal dJ~2 , lequel ne serait pas conservé à la fin de l'étape
C2, mais à un coefficient dans chacun des 16 signaux issus de la décomposition du signal dJ~2 .
De même, en appliquant la même règle que ci-dessus pour le signal dJ~2 , un coefficient du signal dJ~2 devrait être liée à un coefficient dans chacun des 16 signaux issus de la décomposition du signal dJ~ι . Or le signal S^1 issu de cette décomposition est lui-même re-décomposé, notamment en un signal Si/ ~-ι de niveau plus grossier que celui du signal dJ~2 . Afin de respecter le principe du codage "zerotree", on lie les coefficients des signaux S^1 et d^ , non pas aux coefficients du signal dJ~2 , mais aux coefficients du signal dJ~% . Les valeurs des coefficients des signaux S^1 et dûJ \ seront ainsi codées en fonction de celles, théoriquement plus grandes, des coefficients du signal dJ~3. Cette quantification intrinsèque réalisée par le codage "zerotree" est aussi appelée "quantification par approximation successive".
A l'issue de ce codage par "zerotree", on obtient à la fin de l'étape C3 un flux de bits qui code la décomposition en paquets d'ondelettes effectuée à l'étape C2. Les données ainsi obtenues sont de taille beaucoup moins importante qu'à la fin de l'étape C2. En effet, le fait d'exploiter la décroissance des coefficients à travers les échelles, ajouté au fait que l'analyse en ondelettes produit de nombreux coefficients proches de zéro, permet à la méthode de codage "zerotree" d'obtenir un fort taux de compression. De plus, les données obtenues sont organisées par ordre d'importance, comme représenté à la figure 11. Les données ZTO codent des coefficients correspondant au niveau le plus grossier de détail, tandis que les données ZT 1 codent des coefficients de détail à un niveau un peu moins grossier, les données ZT2 des coefficients de détail à un niveau encore plus fin, et ainsi de suite. Les données ZTO correspondent à des informations qui décrivent le plus les données originales. On dispose donc d'une représentation progressive de la texture dans la mesure où les données situées après les données ZTO permettent de raffiner progressivement la représentation grossière de la texture contenue dans ces données ZTO. Ainsi, lorsqu'on transmet seulement les premières données de cette représentation obtenue à la fin de l'étape C3, on obtient une représentation grossière de la texture. En variante, dans cette étape C3, au lieu d'utiliser un codage "zerotree" on utilise un codage de type "Huffman11 dynamique combiné à une quantification scalaire non-uniforme. Notamment la composante Y des données issues de l'étape C2 est moins quantifiée que les composantes U et V. Le pas de cette quantification est par exemple fixé de manière adéquate pour une taille des données compressées fixées. Ce procédé, appelé "Rate Allocation", est utilisé dans la norme "Joint Photographie Experts Group (JPEG) 2000". Pour cela, on calcule par exemple le pas de quantification itérativement jusqu'à atteindre le taux de compression voulu. Ce posttraitement s'avère utile par exemple lors de la transmission des données compressées sur un réseau à un débit fixé. De plus, une telle quantification est adaptable afin de quantifier moins certaines zones d'intérêt de la texture, si de telles zones sont identifiées, par rapport aux autres zones de moindre intérêt.
Cette variante permet de diminuer la complexité des calculs lors de la décompression, mais est beaucoup moins efficace en termes de taux de compression que la variante principale de réalisation de l'invention. Il est à noter qu'il est aussi possible de coupler le codage "zerotree" de la variante principale de l'invention avec un codage de type "Huffman" dynamique, mais cela n'améliorerait que très peu le taux de compression des données obtenues. Le procédé de décodage selon l'invention est maintenant décrit en liaison avec les figures 4 et 12. Les données obtenues à la fin de l'étape C3 sont envoyées par l'ordinateur ORD à un terminal distant T sur un réseau de communication RES. Le flux de données F correspondant contient la représentation des données codées par "zerotree" et organisées par ordre d'importance telle que décrite plus haut en relation avec la figure 11.
A la réception du flux de données F, le terminal T stocke en mémoire toutes les données reçues, ou seulement les premières données, par exemple les données ZTO, ZT 1 et ZT2 si le terminal T a une capacité mémoire limitée, ou si une panne de communication interrompt l'envoi des données juste après l'envoi des données ZT2.
Le terminal T, après décodage canal du signal transportant le flux de données F, décode les données reçues suivant les étapes D1 à D3 représentées à la figure 12. L'étape D1 est la décompression des données reçues. Pour cela le terminal T utilise un algorithme de décodage "zerotree" inverse de celui utilisé à l'étape C3 pour le codage, c'est-à-dire qu'il utilise les mêmes règles d'association des coefficients d'un niveau de résolution à un autre pour retrouver les données issues de la décomposition en paquets d'ondelettes. Si seules les données ZTO, ZT1 et ZT2 sont décompressées, seuls les coefficients des premiers niveaux de résolution de la décomposition en paquets d'ondelettes de l'étape C2 sont obtenus.
Par ailleurs, lors du codage "zerotree", le caractère local de l'analyse en ondelettes est conservé. Ainsi lors du décodage, le terminal T est en mesure de ne décoder qu'une partie des données reçues, afin par exemple de ne rendre la texture que sous certaines directions de points de vue ou certaines directions de la lumière.
L'étape D2 est la synthèse en ondelettes des données décompressées à l'étape D1. Le codage "zerotree" étant fonction de la structure de l'arbre de décomposition en paquets d'ondelettes retenu à l'étape C2, le terminal T reconstitue aisément tout ou partie des données de texture réorganisées et reformatées obtenues à la fin de l'étape C1. Il suffit pour cela d'effectuer des transformées de Haar inverses dans l'ordre de la décomposition en paquets d'ondelettes, dimension par dimension.
Enfin l'étape D3 est la réorganisation en six dimensions des données obtenues à la fin de l'étape D2. Le terminal T obtient ainsi une texture exprimée sous la forme d'une BTF1 utilisable directement pour effectuer son rendu sur un écran. Si seules les données ZTO, ZT1 et ZT2 ont été synthétisées à l'étape D2, cette BTF est en fait une représentation grossière de la texture compressée selon l'invention.

Claims

REVENDICATIONS
1. Procédé de codage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte les étapes de: - analyse en ondelettes (C2) desdites données sur lesdites dimensions,
- et compression (C3) de données obtenues à partir du résultat de ladite analyse (C2).
2. Procédé de codage selon la revendication 1 , caractérisé en ce qu'il comporte une étape préalable de réorganisation (C1) desdites données selon un nombre de dimensions prédéterminé.
3. Procédé de codage selon la revendication 2, caractérisé en ce que dans ladite étape de réorganisation lesdites données sont rangées de manière à maximiser la corrélation entre deux échantillons successifs desdites données selon au moins une dimension.
4. Procédé de codage selon l'une quelconque des revendications 1 à 3, caractérisé en ce que lesdites données représentent des couleurs selon le système de codage couleur YUV.
5. Procédé de codage selon l'une quelconque des revendications 1 à 4, caractérisé en ce que l'étape de compression (C3) utilise un codage de type "zerotree".
6. Procédé de décodage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte les étapes de:
- décompression (D1 ) desdites données,
- et synthèse en ondelettes (D2) sur lesdites dimensions de données obtenues à partir de ladite décompression (D1 ).
7. Signal représentatif d'une texture multidimensionnelle initialement représentée par des données organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce que lesdites données ont été codées par analyse en ondelettes sur lesdites dimensions, puis par compression de données obtenues à partir du résultat de ladite analyse.
8. Dispositif de codage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte:
- des moyens d'analyse en ondelettes desdites données sur lesdites dimensions,
- et des moyens de compression de données obtenues à partir desdits moyens d'analyse.
9. Dispositif de décodage de données représentatives d'une texture multidimensionnelle, lesdites données étant initialement organisées sur un nombre de dimensions au moins égal à trois, une au moins desdites dimensions étant liée à un paramètre de rendu de ladite texture, caractérisé en ce qu'il comporte: - des moyens de décompression desdites données,
- et des moyens de synthèse en ondelettes sur lesdites dimensions de données obtenues à partir desdits moyens de décompression.
10. Programme d'ordinateur comportant des instructions pour mettre en œuvre l'un des procédés selon l'une quelconque des revendications 1 à 6, lorsqu'il est exécuté sur un ordinateur.
EP08762021A 2007-02-01 2008-01-31 Procédé de codage de données répresentatives d'une texture multidimensionnelle, dispositif de codage, procédé et dispositif de décodage, signal et programme correspondants Ceased EP2135221A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0752998 2007-02-01
PCT/FR2008/050161 WO2008110719A1 (fr) 2007-02-01 2008-01-31 Procede de codage de donnees representatives d'une texture multidimensionnelle, dispositif de codage, procede et dispositif de decodage, signal et programme correspondants

Publications (1)

Publication Number Publication Date
EP2135221A1 true EP2135221A1 (fr) 2009-12-23

Family

ID=38654952

Family Applications (1)

Application Number Title Priority Date Filing Date
EP08762021A Ceased EP2135221A1 (fr) 2007-02-01 2008-01-31 Procédé de codage de données répresentatives d'une texture multidimensionnelle, dispositif de codage, procédé et dispositif de décodage, signal et programme correspondants

Country Status (4)

Country Link
US (1) US20100053153A1 (fr)
EP (1) EP2135221A1 (fr)
JP (1) JP5102310B2 (fr)
WO (1) WO2008110719A1 (fr)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2941548A1 (fr) * 2009-01-28 2010-07-30 France Telecom Procede de representation d'un materiau
US8378859B2 (en) 2010-07-16 2013-02-19 Apple Inc. Memory compression technique with low latency per pixel
US8989509B2 (en) 2012-12-18 2015-03-24 Apple Inc. Streaming wavelet transform
JP6410451B2 (ja) * 2014-03-31 2018-10-24 キヤノン株式会社 情報処理装置、計測システム、情報処理方法およびプログラム。
US9392212B1 (en) * 2014-04-17 2016-07-12 Visionary Vr, Inc. System and method for presenting virtual reality content to a user
US9665170B1 (en) 2015-06-10 2017-05-30 Visionary Vr, Inc. System and method for presenting virtual reality content to a user based on body posture
CN105898305B (zh) * 2016-04-12 2019-02-15 上海兆芯集成电路有限公司 基于无损联合图像专家小组格式的图像压缩与解压缩方法
CN110192106B (zh) * 2017-01-16 2021-09-28 株式会社岛津制作所 数据解析装置以及数据解析用程序

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6057884A (en) * 1997-06-05 2000-05-02 General Instrument Corporation Temporal and spatial scaleable coding for video object planes
US6661927B1 (en) * 2000-07-27 2003-12-09 Motorola, Inc. System and method for efficiently encoding an image by prioritizing groups of spatially correlated coefficients based on an activity measure
FR2827409B1 (fr) * 2001-07-10 2004-10-15 France Telecom Procede de codage d'une image par ondelettes permettant une transmission adaptative de coefficients d'ondelettes, signal systeme et dispositifs correspondants
EP1296288B1 (fr) * 2001-09-21 2006-04-19 Interuniversitair Microelektronica Centrum Vzw Un dispositif et méthode pour un codage à blocs avec une mémoire FIFO bidimensionnelle
JP3901644B2 (ja) * 2003-01-30 2007-04-04 株式会社東芝 テクスチャ画像圧縮装置及び方法、テクスチャ画像抽出装置及び方法、データ構造、記憶媒体
FR2856548A1 (fr) * 2003-06-18 2004-12-24 France Telecom Procede de representation d'une sequence d'images par modeles 3d, signal et dispositifs correspondants
FR2876821A1 (fr) * 2004-10-14 2006-04-21 France Telecom Procede de decodage local d'un train binaire de coefficients d'ondelettes
US20070019740A1 (en) * 2005-07-25 2007-01-25 Texas Instruments Incorporated Video coding for 3d rendering
US8340193B2 (en) * 2006-08-04 2012-12-25 Microsoft Corporation Wyner-Ziv and wavelet video coding
US20080095235A1 (en) * 2006-10-20 2008-04-24 Motorola, Inc. Method and apparatus for intra-frame spatial scalable video coding

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO2008110719A1 *

Also Published As

Publication number Publication date
WO2008110719A1 (fr) 2008-09-18
JP5102310B2 (ja) 2012-12-19
US20100053153A1 (en) 2010-03-04
JP2010518667A (ja) 2010-05-27

Similar Documents

Publication Publication Date Title
EP2135221A1 (fr) Procédé de codage de données répresentatives d&#39;une texture multidimensionnelle, dispositif de codage, procédé et dispositif de décodage, signal et programme correspondants
TW202147849A (zh) 點雲壓縮方法、編碼器、解碼器及儲存媒介
Balsa Rodríguez et al. A survey of compressed GPU-based direct volume rendering
Guarda et al. Deep learning-based point cloud coding: A behavior and performance study
Hu et al. An adaptive two-layer light field compression scheme using GNN-based reconstruction
CA2346342C (fr) Compression et codage de reseau maille tridimensionnel
Lin et al. 3d model streaming based on jpeg 2000
Liu et al. Mobile volumetric video streaming system through implicit neural representation
US11893684B1 (en) Systems and methods for signal-based point cloud representation
Feng et al. Neural subspaces for light fields
EP1574068B1 (fr) Procede de codage d&#39;une image par ondelettes et procede de decodage correspondant
Rudolph et al. Learned compression of point cloud geometry and attributes in a single model through multimodal rate-control
FR2876821A1 (fr) Procede de decodage local d&#39;un train binaire de coefficients d&#39;ondelettes
US12469179B2 (en) System and methods for upsampling of decompressed data after lossy compression using a neural network
EP4078959B1 (fr) Procede d&#39;encodage d&#39;une image numerique en vue de sa compression
Cui et al. Palette-based Color Attribute Compression for Point Cloud Data.
WO2006053842A1 (fr) Procede de codage d&#39;images codees par ondelettes a controle de debit, dispositif de codage et programme d&#39;ordinateur correspondants
Hakami Wavelet based multimedia data compression techniques
Freitas Sensing and Reconstruction of Plenoptic Point Clouds
de Carvalho Freitas Sensing and reconstruction of plenoptic point clouds
WO2004112398A1 (fr) Procede et dispositif de codage et de decodage d’une sequence d’images video
Pushpalatha et al. Interpolative Model on Hueristic Projection Transform for Image Compression in Cloud Services.
FR2929431A1 (fr) Procede et dispositif de classification des echantillons representatifs d&#39;un signal numerique d&#39;image
Siddeq Novel methods of image compression for 3D reconstruction
Pratapa et al. RANDM: Random Access Depth Map Compression Using Range-Partitioning and Global Dictionary

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20090813

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC MT NL NO PL PT RO SE SI SK TR

RIN1 Information on inventor provided before grant (corrected)

Inventor name: BARIL, JEROME

Inventor name: GIOIA, PATRICK

17Q First examination report despatched

Effective date: 20091216

DAX Request for extension of the european patent (deleted)
REG Reference to a national code

Ref country code: DE

Ref legal event code: R003

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION HAS BEEN REFUSED

18R Application refused

Effective date: 20121018