3D computer model processing apparatus

• US 20030063086A1
• Filed: 09/26/2002
• Published: 04/03/2003
• Est. Priority Date: 09/28/2001
• Status: Active Grant

• Current Assignee: Canon Europa N.V. (Canon Inc.)
• Original Assignee: Canon Europa N.V. (Canon Inc.)
• Inventors: Baumberg, Adam Michael
• Granted Patent: US 7,079,680 B2
• Time in Patent Office: Days
• US Class Current: 345/420
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 17/205 Re-meshing

Abstract

In a computer processing apparatus 2, a 3D computer model comprising a polygon mesh 500 representing the visual hull of an object 300 is generated by processing images of the object recorded at different positions and orientations to back-project the silhouette of the object in each image to give a respective cone which constrains the volume of 3D space occupied by the object. To remove concave and convex artefacts 510 in the polygon mesh 500, the polygon mesh is projected into each image to give a respective reference silhouette for each image. A change is made to at least one edge or vertex in the polygon mesh to give a refined polygon mesh, which is then projected into each image. The resulting silhouette in each image is tested against the corresponding reference silhouette. If the silhouette of the refined polygon mesh is the same as each reference silhouette, to within an allowable tolerance, then the changed edge or vertex is allowed in the polygon mesh, otherwise the polygon mesh is returned to its previous state. This processing to change and test the polygon mesh is carried out a number of times. Artefacts are removed from the polygon mesh because their removal does not make the polygon mesh inconsistent with the reference silhouettes. Parts of the polygon mesh representing actual features of the object are not changed because such a change causes the polygon mesh to become inconsistent with at least one reference silhouette and therefore such a change is rejected.

Claims

1. A method of processing data defining a plurality of images of an object recorded at different positions and orientations and data defining the positions and orientations, to generate data defining a three-dimensional computer model of the object, the method comprising:

generating a polygon mesh representing the surface of the object, the polygon mesh defining a volume of three-dimensional space constrained by the projection of the respective silhouette of the object from each image into the three-dimensional space; and

performing refinement processing a plurality of times to attempt to refine the polygon mesh, each time by;

amending at least one vertex or edge in the polygon mesh to give a refined polygon mesh having an amendment;

projecting at least part of the refined polygon mesh containing the amendment into a plurality of reference images to give a respective projection silhouette of the refined mesh in each reference image;

testing the projection silhouette of the refined mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

allowing the amendment if the difference between the projection silhouette of the refined mesh and the reference silhouette in each reference image does not exceed a threshold, otherwise rejecting the amendment.

2. A method according to claim 1, further comprising projecting the polygon mesh prior to the refinement processing into each reference image to generate the respective reference silhouette for each reference image.

3. A method according to claim 2, wherein at least some of the reference images comprise images used to generate the polygon mesh.

4. A method according to claim 1, wherein the testing of the projection silhouette of the refined mesh against at least part of a reference silhouette in a reference image comprises:

comparing the projection silhouette of the refined mesh against the at least part of the reference silhouette on a pixel-by-pixel basis to generate a difference image comprising pixels identifying positions where the projection silhouette and reference silhouette do not overlap;

performing erosion processing of the difference image; and

determining the number of pixels identifying positions where the projection silhouette and reference silhouette do not overlap remaining in the difference image after the erosion processing;

and wherein the amendment is allowed if the number of pixels remaining in the difference image after the erosion processing does not exceed a predetermined number, otherwise the amendment is rejected.

5. A method according to claim 1, wherein the amendment to give a refined polygon mesh comprises collapsing at least one edge in the polygon mesh.

6. A method according to claim 1, wherein the amendment to give a refined polygon mesh comprises moving at least one vertex in the polygon mesh.

10. A method according to claim 1 or claim 7, further comprising generating a signal conveying the refined three-dimensional computer model.

11. A method according to claim 10, further comprising making a recording of the signal either directly or indirectly.

31. A storage device storing instructions for causing a programmable processing apparatus to become operable to perform a method as set out in any of claims 1, 7, 23, 24 and 29.

32. A signal carrying instructions for causing a programmable processing apparatus to become operable to perform a method as set out in any of claims 1, 7, 23, 24 and 29.

7. A method of processing data defining (i) a polygon mesh representing the surface of an object, the polygon mesh defining a volume of three-dimensional space constrained by the projection into the three-dimensional space of a respective silhouette of the object from each of a plurality of images recorded at different positions and orientations and (ii) the positions and orientations at which the images were recorded, to attempt to refine the polygon mesh, the method comprising:

amending at least one vertex or edge in the polygon mesh to give an amendment changing the polygon mesh;

projecting at least part of the changed polygon mesh containing the amendment into each of a plurality of reference images to give a respective projection silhouette of the changed mesh in each reference image;

testing the projection silhouette of the changed mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween;

allowing the change to the polygon mesh resulting from the amendment if the difference between the projection silhouette of the changed mesh and the reference silhouette in each reference image does not exceed a threshold, otherwise rejecting the change to the polygon mesh; and

repeating the processing a plurality of times.

8. A method according to claim 7, further comprising projecting the polygon mesh prior to the refinement processing into each reference image to generate the respective reference silhouette for each reference image.

9. A method according to claim 8, wherein at least some of the reference images comprise images used to generate the initial polygon mesh.

12. Apparatus operable to process data defining a plurality of images of an object recorded at different positions and orientations and data defining the positions and orientations, to generate data defining a three-dimensional computer model of the object, the apparatus comprising:

a polygon mesh generator operable to generate data defining a polygon mesh representing the surface of the object, the polygon mesh defining a volume of three-dimensional space constrained by the projection of the respective silhouette of the object from each image into the three-dimensional space; and

a polygon mesh refiner operable to perform refinement processing, the polygon mesh refiner comprising;

a polygon mesh editor operable to amend at least one vertex or edge in the polygon mesh to give a refined polygon mesh having an amendment;

a polygon mesh projector operable to project at least part of the refined polygon mesh containing the amendment into a plurality of reference images to give a respective projection silhouette of the refined mesh in each reference image;

a silhouette tester operable to test the projection silhouette of the refined mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

an amendment selector arranged to allow the amendment if the difference between the projection silhouette of the refined mesh and the reference silhouette in each reference image does not exceed a threshold, otherwise to reject the amendment.

13. Apparatus according to claim 12, further comprising a reference silhouette generator operable to project the polygon mesh prior to processing by the polygon mesh refiner into each reference image to generate the respective reference silhouette for each reference image.

14. Apparatus according to claim 13, wherein at least some of the reference images comprise images used to generate the polygon mesh.

15. Apparatus according to claim 12, wherein the silhouette tester comprises:

a difference image generator operable to compare the projection silhouette of the refined mesh against the at least part of the reference silhouette on a pixel-by-pixel basis to generate a difference image comprising pixels identifying positions where the projection silhouette and reference silhouette do not overlap;

an erosion processor operable to perform erosion processing of the difference image; and

a pixel counter operable to determine the number of pixels identifying positions where the projection silhouette and reference silhouette do not overlap remaining in the difference image after the erosion processing;

and wherein the amendment selector is arranged to allow the amendment if the number of pixels remaining in the difference image after the erosion processing does not exceed a predetermined number, otherwise to reject the amendment.

16. Apparatus according to claim 12, wherein the polygon mesh editor is operable to collapse at least one edge in the polygon mesh.

17. Apparatus according to claim 12, wherein the polygram mesh editor is operable to move at least one vertex in the polygon mesh.

18. Apparatus operable to process data defining (i) a polygon mesh representing the surface of an object, the polygon mesh defining a volume of three-dimensional space constrained by the projection into the three-dimensional space of a respective silhouette of the object from each of a plurality of images recorded at different positions and orientations and (ii) the positions and orientations at which the images were recorded, to attempt to refine the polygon mesh, the apparatus comprising:

a polygon mesh editor operable to amend at least one vertex or edge in the polygon mesh to give an amendment changing the polygon mesh;

a projection silhouette generator operable to project at least part of the changed polygon mesh containing the amendment into each of a plurality of reference images to give a respective projection silhouette of the changed mesh in each reference image;

a difference calculator operable to test the projection silhouette of the changed mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

an amendment selector arranged to allow the change to the polygon mesh resulting from the amendment if the difference between the projection silhouette of the changed mesh and the reference silhouette in each reference image does not exceed a threshold, otherwise to reject the change to the polygon mesh.

19. Apparatus according to claim 18, further comprising a reference silhouette generator operable to project the polygon mesh into each reference image to generate the respective reference silhouette for each reference image.

20. Apparatus according to claim 19, wherein at least some of the reference images comprise images used to generate the initial polygon mesh.

21. Apparatus for processing data defining a plurality of images of an object recorded at different positions and orientations and data defining the positions and orientations, to generate data defining a three-dimensional computer model of the object, the apparatus comprising:

means for generating data defining a polygon mesh representing the surface of the object, the polygon mesh defining a volume of three-dimensional space constrained by the projection of the respective silhouette of the object from each image into the three-dimensional space; and

means for performing refinement processing, comprising;

means for amending at least one vertex or edge in the polygon mesh to give a refined polygon mesh having an amendment;

means for projecting at least part of the refined polygon mesh containing the amendment into a plurality of reference images to give a respective projection silhouette of the refined mesh in each reference image;

means for testing the projection silhouette of the refined mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

amendment selection means arranged to allow the amendment if the difference between the projection silhouette of the refined mesh and the reference silhouette in each reference image does not exceed a threshold, otherwise to reject the amendment.

22. Apparatus for processing data defining (i) a polygon mesh representing the surface of an object, the polygon mesh defining a volume of three-dimensional space constrained by the projection into the three-dimensional space of a respective silhouette of the object from each of a plurality of images recorded at different positions and orientations and (ii) the positions and orientations at which the images were recorded, to attempt to refine the polygon mesh, the apparatus comprising:

means for amending at least one vertex or edge in the polygon mesh to give an amendment changing the polygon mesh;

means for projecting at least part of the changed polygon mesh containing the amendment into each of a plurality of reference images to give a respective projection silhouette of the changed mesh in each reference image;

means for testing the projection silhouette of the changed mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

amendment selection means arranged to allow the change to the polygon mesh resulting from the amendment if the difference between the projection silhouette of the changed mesh and the reference silhouette in each reference image does not exceed a threshold, otherwise to reject the change to the polygon mesh.

23. A method of processing data defining a plurality of images of an object recorded at different positions and orientations and data defining the positions and orientations, to generate data defining a three-dimensional computer model of the object, the method comprising:

generating a polygon mesh representing the surface of the object, the polygon mesh defining a volume of three-dimensional space constrained by the projection of the respective silhouette of the object from each image into the three-dimensional space; and

performing refinement processing a plurality of times, each time by;

amending at least one vertex or edge in the polygon mesh to give a refined polygon mesh having an amendment;

projecting at least part of the refined polygon mesh containing the amendment into a plurality of reference images to give a respective projection silhouette of the refined mesh in each reference image;

testing the projection silhouette of the refined mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

determining amendments for the polygon mesh in dependence upon the differences between the projection silhouette of the refined mesh and the reference silhouette in each reference image.

24. A method of processing data defining (i) a polygon mesh representing the surface of an object, the polygon mesh defining a volume of three-dimensional space constrained by the projection into the three-dimensional space of a respective silhouette of the object from each of a plurality of images recorded at different positions and orientations and (ii) the positions and orientations at which the images were recorded, to change the polygon mesh, the method comprising:

amending at least one vertex or edge in the polygon mesh to give an amendment changing the polygon mesh;

projecting at least part of the changed polygon mesh containing the amendment into each of a plurality of reference images to give a respective projection silhouette of the changed mesh in each reference image;

testing the projection silhouette of the changed mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween;

determining what change to make to the polygon mesh in dependence upon the difference between the projection silhouette of the changed mesh and the reference silhouette in each reference image and making the determined change; and

repeating the processing a plurality of times.

25. Apparatus operable to process data defining a plurality of images of an object recorded at different positions and orientations and data defining the positions and orientations, to generate data defining a three-dimensional computer model of the object, the apparatus comprising:

a polygon mesh generator operable to generate data defining a polygon mesh representing the surface of the object, the polygon mesh defining a volume of three-dimensional space constrained by the projection of the respective silhouette of the object from each image into the three-dimensional space; and

a polygon mesh refiner operable to perform refinement processing, the polygon mesh refiner comprising;

a polygon mesh editor operable to amend at least one vertex or edge in the polygon mesh to give a refined polygon mesh having an amendment;

a polygon mesh projector operable to project at least part of the refined polygon mesh containing the amendment into a plurality of reference images to give a respective projection silhouette of the refined mesh in each reference image;

a silhouette tester operable to test the projection silhouette of the refined mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

an amendment calculator operable to determine what amendments to make to the polygon mesh in dependence upon the difference between the projection silhouette of the refined mesh and the reference silhouette in each reference image.

26. Apparatus operable to process data defining (i) a polygon mesh representing the surface of an object, the polygon mesh defining a volume of three-dimensional space constrained by the projection into the three-dimensional space of a respective silhouette of the object from each of a plurality of images recorded at different positions and orientations and (ii) the positions and orientations at which the images were recorded, to change the polygon mesh, the apparatus comprising:

a polygon mesh editor operable to amend at least one vertex or edge in the polygon mesh to give an amendment changing the polygon mesh;

a projection silhouette generator operable to project at least part of the changed polygon mesh containing the amendment into each of a plurality of reference images to give a respective projection silhouette of the changed mesh in each reference image;

a difference calculator operable to test the projection silhouette of the changed mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

an amendment calculator operable to determine what amendments to make to the polygon mesh in dependence upon the difference between the projection silhouette of the changed mesh and the reference silhouette in each reference image, and to make the determined amendments to the polygon mesh.

27. Apparatus for processing data defining a plurality of images of an object recorded at different positions and orientations and data defining the positions and orientations, to generate data defining a three-dimensional computer model of the object, the apparatus comprising:

means for generating data defining a polygon mesh representing the surface of the object, the polygon mesh defining a volume of three-dimensional space constrained by the projection of the respective silhouette of the object from each image into the three-dimensional space; and

means for performing refinement processing, comprising;

means for amending at least one vertex or edge in the polygon mesh to give a refined polygon mesh having an amendment;

means for projecting at least part of the refined polygon mesh containing the amendment into a plurality of reference images to give a respective projection silhouette of the refined mesh in each reference image;

means for testing the projection silhouette of the refined mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

means for determining what amendments to make to the polygon mesh in dependence upon the difference between the projection silhouette of the refined mesh and the reference silhouette in each reference image.

28. Apparatus for processing data defining (i) a polygon mesh representing the surface of an object, the polygon mesh defining a volume of three-dimensional space constrained by the projection into the three-dimensional space of a respective silhouette of the object from each of a plurality of images recorded at different positions and orientations and (ii) the positions and orientations at which the images were recorded, to change the polygon mesh, the apparatus comprising:

means for amending at least one vertex or edge in the polygon mesh to give an amendment changing the polygon mesh;

means for projecting at least part of the changed polygon mesh containing the amendment into each of a plurality of reference images to give a respective projection silhouette of the changed mesh in each reference image;

means for testing the projection silhouette of the changed mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

amendment selection means for determining what amendments to make to the polygon mesh in dependence upon the difference between the projection silhouette of the changed mesh and the reference silhouette in each reference image, and for making the determined amendments to the polygon mesh.

29. A method of processing data defining a polygon mesh representing the surface of an object to change the polygon mesh, the method comprising:

amending at least one vertex or edge in the polygon mesh to give an amendment changing the polygon mesh;

projecting at least part of the changed polygon mesh containing the amendment into each of a plurality of reference images to give a respective projection silhouette of the changed mesh in each reference image;

testing the projection silhouette of the changed mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween;

determining what change to make to the polygon mesh in dependence upon the difference between the projection silhouette of the changed mesh and the reference silhouette in each reference image and making the determined change.

30. Apparatus operable to process data defining a polygon mesh representing the surface of an object to change the polygon mesh, the apparatus comprising:

a polygon mesh editor operable to amend at least one vertex or edge in the polygon mesh to give an amendment changing the polygon mesh;

a projection silhouette generator operable to project at least part of the changed polygon mesh containing the amendment into each of a plurality of reference images to give a respective projection silhouette of the changed mesh in each reference image;

a difference calculator operable to test the projection silhouette of the changed mesh in each reference image against at least part of a respective reference silhouette in the reference image to determine the differences therebetween; and

an amendment calculator operable to determine what amendments to make to the polygon mesh in dependence upon the difference between the projection silhouette of the changed mesh and the reference silhouette in each reference image, and to make the determined amendments to the polygon mesh.