Motion estimator for coding and decoding image sequences

• US 7,502,413 B2
• Filed: 07/03/2001
• Issued: 03/10/2009
• Est. Priority Date: 07/13/2000
• Status: Expired due to Fees

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Laurent-Chatenet, Nathalie, Robert, Guillaume
• Primary Examiner(s): SENFI, BEHROOZ M
• Application Number:
  US10/332,684
• Publication Number:
  US 20040047415A1
• Time in Patent Office: 2,807 Days
• Field of Search: 348/416, 348/413, 348/699, 348/402, 348/415, 348/409, 348/401, 348/400, 348/390, 348/384, 348/394, 348/395, 348/403, 348/404, 348/407, 348/408, 348/410, 348/411, 348/412, 348/414, 382/236, 382/241, 382/243, 382/238, 382/232, 382/240, 382/248, 375/240.12, 375/240.01, 375/240.09, 375/240.16, 375/240.03
• US Class Current: 375/240.01
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: H04N 19/543 using regions

Abstract

The invention relates to motion estimation and compensation between two given images represented by a polygonal mesh. It provides a solution to the problems of crowding and uncovering of mesh units when the mesh is shifted. More specifically, the invention relates to a method for the encoding of a mesh that represents an image of a moving sequence. According to the invention, such a mesh is larger in size than the image.

Claims

1. Method comprising encoding of a mesh representing an image of a moving sequence, wherein said mesh is larger in size than said image, and associating at least one of the following markers with at least certain of the vertices and/or certain of the faces of said mesh:

an “

internal”

marker,

one face carrying an “

internal”

marker if it has a non-vacant intersection with said image,

and one vertex carrying an “

internal”

marker if it belongs to an “

internal”

face;

an “

entering”

marker,

one vertex carrying an “

entering”

marker if it carries an “

internal”

marker and if it is external to the image,

and one face carrying an “

entering”

marker if at least one of the three vertices that it connects carries an “

entering”

marker.

2. Encoding method according to claim 1 characterized in that, said image having a surface area of N*M pixels, said mesh has a surface area of at least nN*nM pixels, n being an integer greater than or equal to 2.

3. Encoding method according to claim 1, characterized in that said mesh is a hierarchical mesh having at least two mesh levels nested within a mesh pyramid.

4. Encoding method according to claim 1, characterized in that said mesh is a triangular mesh consisting of an arrangement of vertices and triangular faces, each defined by three references to the vertices that they connect, and having three ridges each connecting two of said vertices.

5. Encoding method according to claim 1, characterized in that it implements the following succession of steps:

estimation of the motion of said vertices of said mesh, between two successive images of said sequence;

construction of colorimetric and/or photometric information designed for vertices and/or faces of said mesh carrying said “

entering”

marker.

6. Encoding method according to claim 5, characterized in that said estimation step comprises the following sub-steps:

the optimization of the motion vectors of the vertices of said mesh that carries said “

internal”

marker, so as to minimize a predetermined criterion of error of reconstruction of the following image;

the interpolation and/or extrapolation of motion vectors of the vertices of said mesh that do not carry said “

internal”

marker, in order to fluidify the overall shift of said mesh.

7. Encoding method according to claim 6, characterized in that said interpolation and/or extrapolation step implements a double forward-backward iterative scan, applied to the lowest-level vertices of said mesh pyramid for which said motion vectors of said vertices have been optimized.

8. Encoding method according to claim 6, characterized in that after said estimation step, it implements a step for shifting each of the vertices of said mesh, by applying its own motion vector to it.

9. Encoding method according to claim 6, characterized in that said construction step implements, firstly, an encoding model using finite elements, and secondly an alternative encoding model, the latter being implemented for at least certain regions of said image, as a function of a predetermined error criterion.

10. Encoding method according to claim 6, characterized in that, said construction step implementing a hierarchical encoding model, it comprises the following steps:

the temporary normal projection of said vertices carrying said “

entering”

marker on an edge of said image;

the optimization of said colorimetric and/or photometric information on said vertices and/or said faces of said image, so as to minimize a predetermined criterion of error of reconstruction for the following image;

the repositioning of said vertices carrying said “

entering ”

marker at their pre-projection position, said “

entering”

vertices being carriers of said optimized colorimetric and/or photometric information.

11. Encoding method according to claim 9, characterized in that said specific encoding comprises the following sub-steps:

the construction of the symmetrized image obtained by the application, to said image, of a symmetry that is axial with respect to each of its edges and a symmetry that is central with respect to each of its corners;

the optimization of said colorimetric and/or photometric information on said vertices and/or said faces of said symmetrized image by the application of said alternative model (DCT, fractals, matching pursuit).

12. Encoding method according to claim 1, characterized in that it implements a step for the storage of photometric and/or colorimetric information associated with the vertices and/or faces outgoing from said image.

13. Encoding method according to claim 5, characterized in that, so long as a face of said mesh carries the “

entering”

marker, said construction step implements at least one iteration of the following successive sub-steps;

the optimization of said colorimetric and/or photometric information on said vertices of said “

entering”

face, so as to minimize a predetermined error criterion;

the transmission to a terminal and/or the storage on a data carrier of said optimized colorimetric and/or photometric information.

14. Encoding method according to claim 5, characterized in that, so long as a face of said mesh carries the “

entering”

marker, said construction step implements at least one iteration of the following successive sub-steps;

the preparation of a criterion enabling the evaluation of a quality of image reconstruction obtained by taking account of the current photometric and/or colorimetric information on the vertices of said face;

when said quality is not satisfactory;

the optimization of said colorimetric and/or photometric information on said vertices of said face, so as to minimize a predetermined criterion of error of reconstruction of the following image;

the transmission to a terminal and/or the storage on a data carrier of said optimized colorimetric and/or photometric information;

the transmission and/or storage of a tree of markers providing an indication to said terminal about whether said colorimetric and/or photometric information on the vertices of said “

entering”

face has been optimized or not.

15. Encoding method according to claim 5, characterized in that said step of motion estimation furthermore comprises a sub-step for the construction of a tree of the motion vectors to be transmitted and/or to be stored, the belonging of a motion vector to said tree being determined from a criterion of relevance of the motion applied to said faces of said mesh.

16. Encoding method according to claim 15, characterized in that said criterion of relevance results from a predetermined weighted combination of the following sub-criteria:

a surface sub-criterion, enabling an evaluation of the ratio between the surface area of one face and the mean surface area of the faces of said mesh belonging to the same level of said mesh pyramid;

a sub-criterion of compactness, enabling an evaluation of the ratio between the surface area and the perimeter of a face of said mesh;

a sub-criterion of antagonism of the motions, enabling an evaluation of the antagonism of the motion vectors of vertices of said mesh.

17. Encoding method according to claim 5, characterized in that all the motion vectors of said vertices of said mesh are transmitted and/or stored, an adapted decoder using a predetermined criterion to identify the vectors that have to be taken into account.

18. Encoding method according to claim 1, characterized in that when there is a concealment of at least one vertex concealed by a face comprising at least one concealing vertex, said concealed vertex is fused with said concealing vertex.

19. Encoding method according to claim 1, characterized in that it implements a step for the detection of at least one region of said concealed image during a shifting of said mesh, and a step for the storage of photometric and/or colorimetric information on the concealed region, with a view to possible future use, said information being not processed.

20. Device for encoding a mesh representing an image of a moving sequence wherein said mesh is larger in size than said image, wherein the device comprises an encoder, which associates at least one of the following markers with at least certain of the vertices and/or certain of the faces of said mesh:

an “

internal”

marker,

one face carrying an “

internal”

marker if it has a non-vacant intersection with said image,

and one vertex carrying an “

internal”

marker if it belongs to an “

internal”

face; and

an “

entering”

marker,

one vertex carrying an “

entering”

marker if it carries an “

internal”

marker and if it is external to the image,

and one face carrying an “

entering”

marker if at least one of the three vertices that it connects carries an “

entering”

marker.

21. Method for decoding a mesh representing an image of a moving sequence, wherein said mesh is larger in size than said image, comprising:

associating at least one of the following markers with at least certain of the vertices and/or certain of the faces of said mesh;

an “

internal”

marker,

one face carrying an “

internal”

marker if it has a non-vacant intersection with said image,

and one vertex carrying an “

internal”

marker if it belongs to an “

internal”

face; and

an “

entering”

marker,

one vertex carrying an “

entering”

marker if it carries an “

internal”

marker and if it is external to the image,

and one face carrying an “

entering”

marker if at least one of the three vertices that it connects carries an “

entering”

marker;

decoding the mesh.

22. Device for decoding a mesh representing an image of a moving sequence, wherein said mesh is larger in size than said image, and wherein the device comprises a decoder, which associates at least one of the following markers with at least certain of the vertices and/or certain of the faces of said mesh:

an “

internal”

marker,

one face carrying an “

internal”

marker if it has a non-vacant intersection with said image,

and one vertex carrying an “

internal”

marker if it belongs to an “

internal”

face; and

an “

entering”

marker,

one vertex carrying an “

entering”

marker if it carries an “

internal”

marker and if it is external to the image,

and one face carrying an “

entering”

marker if at least one of the three vertices that it connects carries an “

entering”

marker; and

decodes the mesh.