Discrete linear space sampling method and apparatus for generating digital 3D models

• US 7,257,249 B2
• Filed: 06/12/2003
• Issued: 08/14/2007
• Est. Priority Date: 06/12/2002
• Status: Expired due to Fees

• Current Assignee: Spatial Integrated Systems, Inc.
• Original Assignee: Spatial Integrated Systems, Inc.
• Inventors: Farsaie, Ali
• Primary Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US10/460,707
• Publication Number:
  US 20040027347A1
• Time in Patent Office: 1,524 Days
• Field of Search: 382/154, 382/181, 382/209, 382/217, 382/218, 382/312, 717/108, 717/106, 345/418, 345/419, 348/42, 348/46, 348/47
• US Class Current: 382/154
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: H04N 13/221 using the relative movement between cameras and objects

Abstract

A discrete linear space sampling method and system for generating digital 3D models comprising. A plurality of digital images are acquired of a subject from a respective plurality of image sensor positions near the image sensor location. Candidate 3d-spels are identified, each 3d-spel being an image pixel corresponding to a common point on said subject. Candidate 3d-spels are rejected based on a differential analysis of the candidate 3d-spels, the remaining 3d-spels forming a set of accepted 3d-spels. 3D coordinates are calculated for each accepted 3d-spel, thereby forming a point-cloud of the subject.

Claims

1. A discrete linear space sampling method for generating digital 3D models comprising:

acquiring a plurality of digital images of a subject from a respective plurality of image sensor positions near to an image sensor location;

identifying candidate 3d-spels from the acquired digital images, each 3d-spel being an image pixel corresponding to a common point on said subject, and each 3d-spel corresponding to a pair of acquired pixels, the first acquired pixel of the pair of acquired pixels being selected from one of the plurality of acquired images and the second acquired pixel of the pair of acquired pixels being selected from one of the remaining of the plurality of acquired images;

rejecting candidate 3d-spels based on a differential analysis of the candidate 3d-spels, the remaining 3d-spels forming a set of accepted 3d-spels; and

,

calculating 3D coordinates for each accepted 3d-spel, thereby forming a point-cloud of the subject.

2. The method as set forth in claim 1, further including projecting a predetermined grid or a predetermined set of lines onto the subject when acquiring the plurality of digital images for introducing artificial edges and/or artificial points of color differential on the subject.

3. The method as set forth in claim 1, wherein the image sensor is a camera movable along a linear axis.

4. The method as set forth in claim 1, wherein the image sensor is a fixed linear array of sensors.

5. The method as set forth in claim 1, wherein the subject is at least one object.

6. The method as set forth in claim 1, wherein the subject is a scene or space.

7. A discrete linear space sampling method for generating digital 3D models comprising:

acquiring a plurality of digital images of a subject from a respective plurality of image sensor positions near to an image sensor location;

identifying candidate 3d-spels, each 3d-spel being an image pixel corresponding to a common point on said subject;

rejecting candidate 3d-spels based on a differential analysis of the candidate 3d-spels, the remaining 3d-spels forming a set of accented 3d-spels;

calculating 3D coordinates for each accepted 3d-spel, thereby forming a point-cloud of the subject; and

,

organizing said acquired digital images into a three-dimensional array of pixels having a plurality of rows and a plurality of columns, each row and column corresponding to a two-dimensional pixel position for each of said images, wherein each image occupies a respective position in the third dimension of the array, and wherein each position in the three-dimensional array contains at least one pixel value for the respective pixel position.

8. The method as set forth in claim 7, wherein the rejecting is based on a differential analysis of the at least one pixel value for the respective pixel position corresponding to each candidate 3d-spel.

9. The method as set forth in claim 8, further comprising:

generating a geometric mesh of the scene or object based on the accepted 3d-spels, including determining a visible face of each geometric entity comprising the geometric mesh;

mapping a texture to the geometric mesh including determining which of the plurality of acquired digital images each geometric entity corresponds to and determining for each geometric entity a selected geometric region of the corresponding digital image; and

,

pasting the texture onto the geometric mesh including pasting digital image data from each selected geometric region onto the visible face of the geometric entity of the geometric mesh.

10. The method as set forth in claim 9, wherein the geometric mesh is a triangular mesh and the geometric entity is a triangle.

11. The method as set forth in claim 8, further including filtering the accepted set of 3d-spels comprising:

replacing a plurality of accepted 3d-spels within a sphere of a first predetermined spherical radius with a single representative 3d-spel; and

,

removing accepted 3d-spels determined to be noise and/or determined to be sparsely populated within a sphere of a second predetermined spherical radius.

12. A discrete linear space sampling method for generating digital 3D models comprising:

acquiring a plurality of digital images of a subject from a respective plurality of image sensor positions near to an image sensor location;

identifying candidate 3d-spels, each 3d-spel being an image pixel corresponding to a common point on said subject;

rejecting candidate 3d-spels based on a differential analysis of the candidate 3d-spels, the remaining 3d-spels forming a set of accepted 3d-spels;

calculating 3D coordinates for each accepted 3d-spel, thereby forming a point-cloud of the subject;

repeating the acquiring, identifying, rejecting and calculating for one or more additional image sensor locations with respect to said subject, thereby providing a plurality of sets of digital images and a plurality of sets of 3d-spels; and

,

registering the 3d-spels of the plurality of sets of 3d-spels, thereby creating a merged set of 3d-spels having a common origin.

13. The method as set forth in claim 12, further comprising:

organizing said acquired plurality of sets of digital images into a plurality of sets of three-dimensional arrays of pixels, each array having a plurality of rows and a plurality of columns, each row and column corresponding to a two-dimensional pixel position for each of said images, wherein each image occupies a respective position in the third dimension of the array, and wherein each position in the three-dimensional array contains at least one pixel value for the respective pixel position.

14. The method as set forth in claim 13, wherein the rejecting is based on a differential analysis of the at least one pixel value for the respective pixel position corresponding to each candidate 3d-spel.

15. The method as set forth in claim 14, further comprising:

generating a geometric mesh of the scene or object based on the merged set of accepted 3d-spels, including determining a visible face of each geometric entity comprising the geometric mesh;

mapping a texture to the geometric mesh including determining which of the plurality of acquired digital images each geometric entity corresponds to and determining for each geometric entity a selected geometric region of the corresponding digital image; and

,

pasting the texture onto the geometric mesh including pasting digital image data from each selected geometric region onto the visible face of the geometric entity of the geometric mesh.

16. The method as set forth in claim 15, wherein the geometric mesh is a triangular mesh and the geometric entity is a triangle.

17. The method as set forth in claim 14, further including filtering the merged set of 3d-spels comprising:

replacing a plurality of 3d-spels of the merged set of 3d-spels within a sphere of a first predetermined spherical radius with a single representative 3d-spel; and

,

removing 3d-spels of the merged set of 3d-spels determined to be noise and/or determined to be sparsely populated within a sphere of a second predetermined spherical radius.

18. The method as set forth in claim 12, wherein the registering comprises applying known transformations to the image sensor locations.

19. The method as set forth in claim 18, wherein the applying known transformations includes determining homogeneous coordinates and applying affine transformations.

20. The method as set forth in claim 12, wherein the registering comprises applying unknown transformations to the plurality of image sensor coordinate systems.

21. The method as set forth in claim 20, wherein the applying unknown transformations includes:

determining a first set of three points from a first image sensor location and a second set of three matching points from a second image sensor location;

aligning respective image sensor coordinate systems according to the first and second sets of three matching points; and

,

repeating the determining and aligning steps at remaining image sensor locations.

22. The method as set forth in claim 12, wherein the additional image sensor locations include additional image sensors.

23. The method as set forth in claim 12, further including rotating the subject.

24. A system for generating digital 3D models comprising:

means for acquiring a plurality of digital images of a subject from a respective plurality of image sensor positions near to an image sensor location;

means for identifying candidate 3d-spels from the acquired digital images, each 3d-spel being an image pixel corresponding to a common point on said subject, and each 3d-spel corresponding to a pair of acquired pixels, the first acquired pixel of the pair of acquired pixels being selected from one of the plurality of acquired images and the second acquired pixel of the pair of acquired pixels being selected from one of the remaining of the plurality of acquired images;

means for rejecting candidate 3d-spels based on a differential analysis of the candidate 3d-spels, the remaining 3d-spels forming a set of 3d-spels; and

,

means for calculating 3D coordinates for each accepted 3d-spel, thereby forming a point-cloud of the subject.

25. The system as set forth in claim 24, further including means for projecting a predetermined grid or a predetermined set of lines onto the subject when acquiring the plurality of digital images for introducing artificial edges and/or artificial points of color differential on the subject.

26. The system as set forth in claim 24, wherein the image sensor is a camera movable along a linear axis.

27. The system as set forth in claim 24, wherein the image sensor is a fixed linear array of sensors.

28. The system as set forth in claim 24, wherein the subject is at least one object.

29. The system as set forth in claim 24, wherein the subject is a scene or space.

30. A system generating digital 3D models comprising:

means for acquiring a plurality of digital images of a subject from a respective plurality of image sensor positions near to an image sensor location;

means for identifying candidate 3d-spels, each 3d-spel being an image pixel corresponding to a common point on said subject;

means for rejecting candidate 3d-spels based on a differential analysis of the candidate 3d-spels, the remaining 3d-spels forming a set of accented 3d-spels;

means for calculating 3D coordinates for each accented 3d-spel, thereby forming a point-cloud of the subject; and

,

means for organizing said acquired digital images into a three-dimensional array of pixels having a plurality of rows and a plurality of columns, each row and column corresponding to a two-dimensional pixel position for each of said images, wherein each image occupies a respective position in the third dimension of the array, and wherein each position in the three-dimensional array contains at least one pixel value for the respective pixel position.

31. The system as set forth in claim 30, wherein the rejecting is based on a differential analysis of the at least one pixel value for the respective pixel position corresponding to each candidate 3d-spel.

32. The system as set forth in claim 31, further comprising:

means for generating a geometric mesh of the scene or object based on the accepted 3d-spels, including means for determining a visible face of each geometric entity comprising the geometric mesh;

means for mapping a texture to the geometric mesh including determining which of the plurality of acquired digital images each geometric entity corresponds to and means for determining for each geometric entity a selected geometric region of the corresponding digital image; and

,

means for pasting the texture onto the geometric mesh including pasting digital image data from each selected geometric region onto the visible face of the geometric entity of the geometric mesh.

33. The system as set forth in claim 32, wherein the geometric mesh is a triangular mesh and the geometric entity is a triangle.

34. The system as set forth in claim 31, further including means for filtering the accepted set of 3d-spels comprising:

means for replacing a plurality of accepted 3d-spels within a sphere of a first predetermined spherical radius with a single representative 3d-spel; and

,

means for removing accepted 3d-spels determined to be noise and/or determined to be sparsely populated within a sphere of a second predetermined spherical radius.

35. A system generating digital 3D models comprising:

means for acquiring a plurality of digital images of a subject from a respective plurality of image sensor positions near to an image sensor location;

means for identifying candidate 3d-spels, each 3d-spel being an image pixel corresponding to a common point on said subject;

means for rejecting candidate 3d-spels based on a differential analysis of the candidate 3d-spels, the remaining 3d-spels forming a set of accented 3d-spels;

means for calculating 3D coordinates for each accented 3d-spel, thereby forming a point-cloud of the subject;

means for repeating the acquiring, identifying, rejecting and calculating for one or more additional image sensor locations, thereby providing a plurality of sets of digital images and a plurality of sets of 3d-spels; and

,

means for registering the 3d-spels of the plurality of sets of 3d-spels, thereby creating a merged set of 3d-spels having a common origin.

36. The system as set forth in claim 35, further comprising:

means for organizing said acquired plurality of sets of digital images into a plurality of sets of three-dimensional arrays of pixels, each array having a plurality of rows and a plurality of columns, each row and column corresponding to a two-dimensional pixel position for each of said images, wherein each image occupies a respective position in the third dimension of the array, and wherein each position in the three-dimensional array contains at least one pixel value for the respective pixel position.

37. The system as set forth in claim 36, wherein the rejecting is based on a differential analysis of the at least one pixel value for the respective pixel position corresponding to each candidate 3d-spel.

38. The system as set forth in claim 37, further comprising:

means for generating a geometric mesh of the scene or object based on the merged set of accepted 3d-spels, including means for determining a visible face of each geometric entity comprising the geometric mesh;

means for mapping a texture to the geometric mesh including means for determining which of the plurality of acquired digital images each geometric entity corresponds to and determining for each geometric entity a selected geometric region of the corresponding digital image; and

,

means for pasting the texture onto the geometric mesh including pasting digital image data from each selected geometric region onto the visible face of the geometric entity of the geometric mesh.

39. The system as set forth in claim 38, wherein the geometric mesh is a triangular mesh and the geometric entity is a triangle.

40. The system as set forth in claim 37, further including means for filtering the merged set of 3d-spels comprising:

means for replacing a plurality of 3d-spels of the merged set of 3d-spels within a sphere of a first predetermined spherical radius with a single representative 3d-spel; and

,

means for removing 3d-spels of the merged set of 3d-spels determined to be noise and/or determined to be sparsely populated within a sphere of a second predetermined spherical radius.

41. The system as set forth in claim 35, wherein the registering means comprises means for applying known transformations to the image sensor locations.

42. The system as set forth in claim 41, wherein the applying known transformations includes determining homogeneous coordinates and applying affine transformations.

43. The system as set forth in claim 35, wherein the registering means comprises means for applying unknown transformations to the plurality of image sensor coordinate systems.

44. The system as set forth in claim 43, wherein the means for applying unknown transformations includes:

means for determining a first set of three points from a first image sensor location and a second set of three matching points from a second image sensor location;

means for aligning respective image sensor coordinate systems according to the first and second sets of three matching points; and

,

means for repeating the determining and aligning steps at remaining image sensor locations.

45. The system as set forth in claim 35, further including a plurality of image sensors, each image sensor configured to acquire a respective plurality of digital images of the subject from a respective image sensor location, each image of the respective plurality of digital images acquired from a position offset from the remaining positions near the respective sensor location.

46. The system as set forth in claim 35, further including a means for rotating the subject.