Method and apparatus for modeling via a three-dimensional image mosaic system

• US 6,819,318 B1
• Filed: 07/17/2000
• Issued: 11/16/2004
• Est. Priority Date: 07/23/1999
• Status: Expired due to Fees

• Current Assignee: Technest Holdings, Inc. (AccelPath, Inc.)
• Original Assignee: Geng Z. Jason
• Inventors: Geng, Z. Jason
• Primary Examiner(s): Wong, Don
• Assistant Examiner(s): MANCUSO, HUEDUNG XUAN CAO
• Application Number:
  US09/617,867
• Time in Patent Office: 1,583 Days
• Field of Search: 345/419, 345/420, 345/584, 382/154, 382/294, 382/284
• US Class Current: 345/420
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2200/32 involving image mosaicing

Abstract

An imaging method and system for 3D modeling of a 3D surface forms a mosaic from multiple uncalibrated 3D images, without relying on camera position data to merge the 3D images. The system forms the 3D model by merging two 3D images to form a mosaiced image, merging the mosaiced image with another 3D image, and repeating the merging process with new 3D images one by one until the 3D model is complete. The images are aligned in a common coordinate system via spatial transformation and preferably merged using a fuzzy weighting average function to smooth boundary areas between 3D images. The 3D model may be compressed using image compression techniques. In one embodiment, a 2D texture/color overlay is placed over the 3D model to provide a more realistic representation of the object being modeled.

Claims

1. A method for three-dimensional (3D) modeling of a 3D surface, comprising the steps of:

obtaining a plurality of uncalibrated 3D images;

selecting a pair of 3D images out of the plurality of uncalibrated 3D images;

integrating the pair of 3D images to form a mosaiced image by matching one or more surface features common to both images in the pair of 3D images; and

repeating the integrating step by integrating the mosaiced image and a subsequent selected 3D image out of the plurality of uncalibrated 3D images as the pair of 3D images until a 3D model is completed.

2. The method of claim 1, wherein the step of integrating the pair of 3D images includes the steps of:

filtering the pair of 3D images to remove unwanted areas of the 3D images;

aligning the pair of 3D images in a selected global coordinate system; and

merging the pair of 3D images to form the mosaiced image.

3. The method of claim 2, wherein the aligning step conducts alignment based on a surface feature that is independent from a coordinate system definition or an illumination condition.

4. The method of claim 2, wherein the merging step includes the step of blending a boundary between the pair of 3D images.

5. The method of claim 1, wherein the subsequent 3D image selected from the plurality of uncalibrated 3D images is a 3D image that overlaps the mosaiced image and covers an area adjacent to an area covered by the mosaiced image.

6. The method of claim 2, wherein the aligning step includes the steps of:

selecting a first set of fiducial points on one of said pair of 3D images;

selecting a second set of fiducial points on the other of said pair of 3D images;

wherein said first and second sets of fiducial points correspond to overlapping portions of said pair of 3D images; and

aligning corresponding fiducial points between said first and second sets of fiducial points to join the pair of 3D images to form the mosaiced image.

7. The method of claim 6, wherein the step of aligning the corresponding fiducial points includes the step of deriving a spatial transformation matrix via a least squares minimization method to align the pair of 3D images into a common coordinate system.

8. The method of claim 4, wherein the blending step includes the steps of:

determining a boundary area between overlapping portions of the pair of 3D images;

smoothing the boundary area using a fuzzy weighting averaging function; and

conducting a re-sampling operation by sampling a plurality of points on the 3D surface and calculating 3D coordinates using an interpolation algorithm on the sampled points.

9. The method of claim 1, further comprising the step of compressing the 3D model via an image compression process.

10. The method of claim 9, wherein the compressing step conducts compression via a multi-resolution triangulation algorithm, which includes the steps of:

expressing the 3D model as 3D polygons;

converting the 3D polygons from the expressing step into 3D triangles;

iteratively removing triangulation vertices from the 3D triangles to generate a reduced 3D model; and

calculating a 3D distance between the 3D model and the reduced 3D model.

11. The method of claim 1, further comprising the step of overlaying a two-dimensional (2D) texture/color overlay over the 3D model.

12. An apparatus for three-dimensional (3D) modeling of a 3D surface, comprising:

an optical device that obtains a plurality of uncalibrated 3D images that include data corresponding to a distance between a focal point of the optical device and a point on the 3D surface; and

a processor coupled to the optical device that includes;

a selector that selects a pair of 3D images out of the plurality of uncalibrated 3D images obtained by the optical device; and

an integrator that integrates the pair of 3D images to form a mosaiced image by matching one or more surface features common to both images in the pair of 3D images,

wherein the integrator repeats the integration process by integrating the mosaiced image and a subsequent 3D image selected from of the plurality of uncalibrated 3D images as the pair of 3D images until a 3D model is completed.

13. The apparatus of claim 12, wherein the processor further includes a filter that removes undesired areas of the 3D images before the integrator integrates the 3D images.

14. The apparatus of claim 12, wherein the integrator integrates the 3D images by aligning the pair of 3D images in a selected global coordinate system based on a surface feature that is independent from a coordinate system definition and merging the pair of 3D images to form the mosaiced image.

15. The apparatus of claim 12, wherein the integrator integrates the 3D images by

selecting a first set of fiducial points on one of said pair of 3D images;

selecting a second set of fiducial points on the other of said pair of 3D images, wherein said first and second sets of fiducial points correspond to overlapping portions of said pair of 3D images; and

aligning corresponding fiducial points between said first and second sets of fiducial points to join the pair of 3D images to form the mosaiced image.

16. The apparatus of claim 15, wherein the integrator aligns the corresponding fiducial points by deriving a spatial transformation matrix via a least square minimization method to align the pair of 3D images into a common coordinate system.

17. The apparatus of claim 15, wherein the integrator lends a boundary between 3D images by:

determining a boundary area between overlapping portions of the pair of 3D images;

smoothing the boundary area using a fuzzy weighting averaging function; and

conducting a re-sampling operation by sampling a plurality of points on the 3D surface and calculating 3D coordinates using an interpolation algorithm on the sampled points.

18. The apparatus of claim 12, wherein the processor further comprises a compressor that compresses data corresponding to the 3D model.

19. The apparatus of claim 18, wherein the compressor step conducts compression via a multi-resolution triangulation algorithm by:

expressing the 3D model as 3D polygons;

converting the 3D polygons into 3D triangles;

iteratively removing triangulation vertices from the 3D triangles to generate a reduced 3D model; and

calculating a 3D distance between the 3D model and the reduced 3D model.

20. The apparatus of claim 12, wherein the processor further comprises an overlay mechanism that overlays the 3D model with a two-dimensional (2D) texture/color overlay.

21. A system for three-dimensional (3D) modeling of a 3D surface, comprising:

means for obtaining a plurality of uncalibrated 3D images;

means for selecting a pair of 3D images out of the plurality of uncalibrated 3D images; and

means for integrating a pair of 3D images to form a mosaiced image by matching one or more surface features common to both images; and

wherein said means for integrating repeatedly integrates the mosaiced image with another 3D image from the plurality of uncalibrated 3D images until a 3D model is completed.

22. The system of claim 21, wherein the means for integrating further comprise:

means for filtering the pair of 3D images to remove unwanted areas of the 3D images;

means for aligning the pair of 3D images in a selected global coordinate system; and

means for merging the pair of 3D images to form the mosaiced image.

23. The system of claim 22, wherein the means for merging include means for blending a boundary between the pair of 3D images.

24. The system of claim 22, wherein the means for aligning include:

means for selecting a first set of fiducial points on one of said pair of 3D images;

means for selecting a second set of fiducial points on the other of said pair of 3D images, wherein said first and second sets of fiducial points correspond to overlapping portions of said pair of 3D images; and

means for aligning corresponding fiducial points between said first and second sets of fiducial points to join the pair of 3D images to form the mosaiced image.

25. The system of claim 24, wherein the means for aligning the corresponding fiducial points include means for deriving a spatial transformation matrix via a least squares minimization method to align the pair of 3D images into a common coordinate system.

26. The system of claim 23, wherein the means for blending a boundary include:

means for determining a boundary area between overlapping portions of the pair of 3D images;

means for smoothing the boundary area using a fuzzy weighting averaging function; and

means for conducting a re-sampling operation by sampling a plurality of points on the 3D surface and calculating 3D coordinates using an interpolation algorithm on the sampled points.

27. The system of claim 21, further comprising means for compressing the 3D model via an image compression process.

28. The system of claim 27, wherein the means for compressing conduct compression via a multi-resolution triangulation algorithm and further comprise:

means for expressing the 3D model as 3D polygons;

means for converting the 3D polygons from the expressing step into 3D triangles;

means for iteratively removing triangulation vertices from the 3D triangles to generate a reduced 3D model; and

means for calculating a 3D distance between the 3D model and the reduced 3D model.

29. The system of claim 21, further comprising means for overlaying a two-dimensional (2D) texture/color overlay over the 3D model.