Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-07-02
2004-09-21
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S426000, C345S582000, C345S586000
Reexamination Certificate
active
06795070
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention concerns the field of the coding of fixed or animated images with flowrate reduction (compression).
The techniques for compressing images are traditionally used to reduce the flowrate of video numerical signals so as to transmit or store them. The coding method put forward in the first application is particularly adapted to low flowrate transmissions and transmissions without any flowrate guarantee, such as those effected with the IP protocol (Internet Protocol).
2. Description of the Related Art
There are many methods for coding fixed or animated images with flowrate reduction, the most well-known being those having given rise to a standard, such as ISO-JPEG or ISO-MPEG.
These coding methods make use of general compression principles exploiting in fixed images (JPEG) the spatial redundancy inside an image, the correlations between adjacent points and the lower sensibility of the eye to fine details, and in animated images (MPEG) the temporal redundancy between successive images.
In this type of method, first of all the image undergoes a transformation by applying a Discrete Cosinus Transform (DCT) on blocks of the image or by applying a wavelets transform on the whole image. The resulting signal is then quantified so as to limit the number of possible values of the signal, then coded with the aid of an entropic coding using the statistical redundancies of the quantified signal so as to reduce the amount of data to be transmitted or stored.
However, these traditional methods have several limitations due mainly to the use of techniques not taking s account of the contents of the image and their purely numerical character:
ringings due to block effects in the case of the discrete cosinus transform appearing close to the contours of the image, these ringings also appearing in the case of low flowrate wavelets;
these techniques are poorly adapted to geometrical handlings (homothetic transformation, etc) which are traditionally used to determine the compensation of movement between two images in the case of animated images (MPEG) or to integrate synthetic images in natural scenes.
There are also methods acting directly in the spatial area of the image and consisting of generating a photometric surface characterising each chromatic component of the image by directly selecting pixels characteristic of the image, the obtaining of the other pixels of the image being effected via the interpolation of the characteristic pixels.
Although offering a large number of possibilities concerning geometrical handlings, these methods nevertheless prove to be extremely deceptive concerning compression. Moreover, they do not make it possible to obtain a volume of data at the end of coding which is adapted to the complexity of the image and the desired quality of representation contrary to the case with coding by wavelets. In particular, these methods do not make it possible to obtain an image with an acceptable quality, especially when the flowrate is weak.
In addition, there are coding methods using a hierarchical meshing comprising a plurality of nested meshings as described in the article entitled “Progressive coding of 3-D graphic models”, proceedings of the IEEE, June 1998, IEEE, USA, vol. 86, n
o
6, pages 1052-1053. The method is based on a neighbourhood criterion and distinguishes non-essential edges coplanar with their neighbourhood, and the visually important edges, which are significantly different from their neighbourhood. The position values are coded considered as attributes of the edges. So as to limit the number of bits at the end of the coding method, the structure data of the meshing and the attributes of the tops of the meshing are coded by referring to tables.
OBJECTS AND SUMMARY OF THE INVENTION
One aim of the invention is to offer another coding method for mitigating said drawbacks.
The object of the invention is a method for coding a numerical image for producing a binary train representative of said image, the length of the binary train depending on the desired quality of representation, and is characterised in that it comprises the following steps:
a) defining on the area of the image to be coded a hierarchical meshing comprising a plurality of nested meshings whose mesh tops are pixels of said image;
b) determining for each mesh of said hierarchical meshing a luminance deviation between the image to be coded and an interpolated image obtained from the tops of the nested meshing to which the mesh in question belongs, and
c) introducing into the binary train the position, luminance and chrominance values of the tops of the meshes whose luminance deviation is greater than a threshold deviation.
The hierarchical meshing is preferably obtained by regular and successive subdivisions of meshes of a meshing with a coarser base.
So as to more easily process the chrominance, luminance and position values of the tops of the meshes, the method of the invention advantageously comprises a step for embodying a tree structure associated with said hierarchical meshing.
According to one particular embodiment, step c) is repeated several times with increasingly weaker threshold deviations so as to generate on each iteration a group of bits for improving quality of representation.
So as to reduce the size of the binary train, the values to be introduced into the binary train firstly undergo a quantification and compression operation.
Finally, according to another particular embodiment, it is also possible to optimise the position of the tops of the multiple meshing and the associated chrominance and luminance values so as to further increase the quality of representation of the binary train.
REFERENCES:
patent: 5691768 (1997-11-01), Civanlar et al.
patent: 6208997 (2001-03-01), Sigeti et al.
patent: 6262737 (2001-07-01), Li et al.
patent: 6573890 (2003-06-01), Lengyel
Li et al. “Progressive Coding of 3-D Graphic Models”, Jun. 1998, IEEE USA, vol. 86, No. 6, pp. 1052-1063.
Salembier et al. “Very Low Bit Rate Video Coding Using Active Triangular Mesh” 1996 IEEE International Conference on Acoustics, Speech and Signal Processing—Proceedings (ICASSP) May 1996, vol. 4, pp. 2060-2063.
Wang et al. “Use of Two-Dimensional Deformable Mesh Structures for Video Coding, Part II—The Analysis Problem and a Region-Based Coder Employing an Active Mesh Representation”, IEEE, Dec. 1996, vol. 6, No. 6, pp. 647-659.
Lee et al. “Non-Uniform Image Sampling and Interpolation Over Deformed Meshes and Its Hierarchical Extension”, SPEI, May 1995, vol. 2501, pp. 389-400.
Lechat et al. “Image Approximation by Minimization of a Geometric Distance Applied to a 3D Finite Elements Based Model”, IEEE Oct. 1997, vol. 2, pp. 724-727.
Labelle, “Computation of Image Representation Based on Active Triangular Meshes Through Geometrical Surface Evolution”, Feb. 1997, SPIE, vol. 3024, pp. 843-854.
Lee et al, “Two-Dimensional Split and Merge Algorithm for Image Coding”, May 1995, SPIE, Vo. 2501, pp. 694-704.
Laurent-Chatenet Nathalie
Lechat Patrick
Sanson Henri
France Telecom (SA)
Nguyen Kimbinh T.
Patterson Thuente Skaar & Christensen P.A.
LandOfFree
Method for compressing and encoding three-dimensional meshed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for compressing and encoding three-dimensional meshed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for compressing and encoding three-dimensional meshed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3245295