Methods for registration of three-dimensional frames to create three-dimensional virtual models of objects

• US 20020006217A1
• Filed: 04/13/2001
• Published: 01/17/2002
• Est. Priority Date: 04/28/2000
• Status: Active Grant

• Current Assignee: Orametrix Incorporated
• Original Assignee: Orametrix Incorporated
• Inventors: Weise, Thomas, Imgrund, Hans, Sporbert, Peer, Rubbert, Rudger, Kouzian, Dimitrij
• Granted Patent: US 7,027,642 B2
• Time in Patent Office: Days
• US Class Current: 382/131
• CPC Class Codes: A61C 7/00 Orthodontics, i.e. obtaining or maintaining the desired position of teeth, e.g. by straightening, evening, regulating, separating, or by correcting malocclusions
• CPC Class Codes: A61C 7/002 Orthodontic computer assisted systems
• CPC Class Codes: A61C 7/146 Positioning or placement of brackets; Tools therefor
• CPC Class Codes: A61C 9/0053 Optical means or methods, e.g. scanning the teeth by a laser or light beam
• CPC Class Codes: A61F 2002/30953 using a remote computer network, e.g. Internet
• CPC Class Codes: B33Y 50/00 Data acquisition or data processing for additive manufacturing
• CPC Class Codes: B33Y 80/00 Products made by additive manufacturing
• CPC Class Codes: G06T 2207/30004 Biomedical image processing
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/35 using statistical methods
• CPC Class Codes: G06V 10/16 using multiple overlapping images; Image stitching
• CPC Class Codes: G06V 2201/03 Recognition of patterns in medical or anatomical images
• CPC Class Codes: G06V 2201/12 Acquisition of 3D measurements of objects
• CPC Class Codes: G16H 20/40 relating to mechanical, radiation or invasive therapies, e.g. surgery, laser therapy, dialysis or acupuncture

Abstract

A method and system are provided for constructing a virtual three-dimensional model of an object using a data processing system, and at least one machine-readable memory accessible to said data processing system. A set of at least two digital three-dimensional frames of portions of the object are obtained from a source, such as a computing system coupled to an optical or laser scanner, CT scanner, Magnetic Resonance Tomography scanner or other source. The at least two frames comprise a set of point coordinates in a three dimensional coordinate system providing differing information of the surface of the object. The frames provide a substantial overlap of the represented portions of the surface of the object, but do not coincide exactly for example due to movement of the scanning device relative to the object between the generation of the frame. Data representing the set of frames are stored in the memory. The data processing system processes the data representing the set of frames with said data processing system so as to register the frames relative to each other to thereby produce a three-dimensional virtual representation of the portion of the surface of the object covered by said set of frames. The registration is performed without using pre-knowledge about the spatial relationship between the frames. The three-dimensional virtual model or representation is substantially consistent with all of the frames.

Claims

1. A method of constructing a virtual three-dimensional model of an object from a scanner, a data processing system, and at least one machine-readable memory accessible to said data processing system, comprising the steps of:

(a) scanning the object with the scanner and thereby obtaining at least two two-dimensional images of the object, wherein during scanning the scanner and object are moved relative to each other resulting in each image being taken from a different position relative to the surface of the object;

(b) processing said data representing said set of images with said data processing system so as to convert each of said two-dimensional images into a data representing a frame and thereby generate a set of frames corresponding to said images, said set of frames comprising a cloud of individual points, each point in each frame expressed as a location in a three-dimensional coordinate system;

(c) storing data representing said set of frames in said memory; and

(d) further processing said data representing said set of frames with said data processing system so as to register said frames relative to each other to thereby produce a three-dimensional virtual model of the object substantially consistent with all of said frames.

2. The method of claim 1, wherein step (d) comprises the step of performing a frame to frame registration of said set of frames, wherein each frame is registered with respect to one other frame in said set of frames.

3. The method of claim 1, wherein step (d) comprises the step of performing a cumulative registration of said set of frames, wherein at least some of said frames are registered to a plurality of other frames previously having been registered to other frames in said set of frames.

4. The method of claim 1, wherein step (d) comprises performing a frame to frame registration of said set of frames, wherein each frame is registered with respect to one other frame in said set of frames, and thereafter performing a cumulative registration of said frames wherein at least some of said frames are registered to a plurality of other frames previously having been registered to other frames in said set of frames.

5. The method of claim 1, wherein in step (d) one of said frames is a starting frame for registration, and wherein a spatial transformation relationship is derived for each of the other frames in said set of frames and stored in said memory, said spatial transformation relationship indicating how the points in said frame should be translated and rotated in a three-dimensional coordinate system to register said frames relative to said starting frame.

6. The method of claim 5, wherein said starting frame corresponds to the first image captured by said scanner.

7. The method of claim 5, wherein said starting frame corresponds to selected image taken of the object and in which other images were taken of the object in the same vicinity of the object such that a substantial amount of overlap exists between said selected image and said other images.

8. The method of claim 1, wherein, in step (d), said set of frames are registered to each other in a sequential order with the order determined, at least in part, upon the degree of overlap in coverage of said object in said frames.

9. The method of claim 1, wherein said scanner comprises a hand-held scanning device and said object is scanned by moving said hand-held scanning device over said object.

10. The method of claim 9, wherein said object comprises a human.

11. The method of claim 10, wherein said object comprises teeth and associated anatomical structures.

12. The method of claim 9, wherein said object comprises a model of an anatomical structure of a human.

13. The method of claim 1, wherein said data processing system is incorporated into a work station for said scanner.

14. The method of claim 1, wherein said data processing system comprises a general purpose computer operatively connected to said scanner and said memory.

15. The method of claim 1, wherein said data processing system comprises at least two independent processors sharing the processing required by steps (c) and (d).

16. The method of claim 15, wherein one of said processors is incorporated into a work station for said scanner and wherein the other processors comprises a computer remote from said work station.

17. The method of claim 16, wherein said object comprises teeth and associated anatomical structures, and wherein said work station and scanner are located in an orthodontic clinic, and wherein said computer remote from said work station comprises a computer in said orthodontic clinic.

18. The method of claim 1, wherein said scanner, said memory and said data processing system are housed in a single unit.

19. The method of claim 1, wherein said data processing system is coupled to a user interface including a display, and wherein data processing system is operative to display said virtual three dimensional model on said display.

20. An orthodontic scanning system performing the method of any of claims 1-19.

21. A method of registering a first frame, representing a first set of three-dimensional coordinates of points on the surface of an object, relative to second frame, representing a second set of three-dimensional coordinates of points on the surface of the object, comprising the steps of:

storing said sets of three-dimensional coordinates of points in a machine-readable memory;

processing said sets of three-dimensional coordinates with a data processing unit reading said machine-readable memory, said step of processing comprising the steps of;

a) determining Δ

X, Δ

Y and Δ

Z offsets between overlapping points in said frames;

b) changing the coordinates in second frame in accordance with said Δ

X, Δ

Y and Δ

Z offsets;

c) computing a surface for said first frame from points in said first frame;

d) computing normal vectors from said points in said second frame to said surface and a net normal vector;

e) determining X, Y and Z components of a rotation matrix from said surface and said points in said second frame, said rotation matrix indicting the amount of rotation required to fit said second frame to said first frame; and

f) applying said net normal vector and said rotation matrix to said points in said second frame to thereby generate a new set of coordinates of said second frame in three dimensions to fit of said second frame to said first frame.

22. The method of claim 21, further comprising the following steps:

g) determining the closeness of said fit of said second frame to said first frame;

h) comparing said closeness to a quality index; and

i) repeating steps at least steps c), d), e) and f) for said second frame, after application of step f), to said first frame.

23. The method of claim 22, wherein steps c)-i) are repeated numerous times until said closeness in step h) is less than or equal to said quality index.

24. The method of claim 21, wherein said first frame comprises a set of coordinates of said object arrived at after a cumulative registration of a set of frames of said object.

25. The method of claim 21, wherein said first frame comprises at least two frames previously registered with respect to each other.

26. The method claim 21, wherein said method is performed while a scanning system captures a plurality of images of the object, said scanning system comprising an electronic imaging device generating a stream of images and supplying said images to said memory.

27. The method of claim 26, wherein said scanning system includes said memory and said data processing unit, and wherein said scanning system further comprises a user interface including a display, and wherein the results of fitting said second frame to said first frame are displayed on said display while said scanning system is capturing said plurality of images, enabling the operator of said scanning system to see the results of scanning the object.

28. The method of claim 27, wherein said object comprises a human.

29. The method of claim 28, wherein said object comprises teeth and associated anatomical structures.

30. The method of claim 28, wherein said scanning system comprises a hand-held scanner.

31. The method of claim 21, wherein in step (a) a two dimensional cross-correlation is performed by said data processing unit on first and second images corresponding to said first and second frames to determine said Δ

X and Δ

Y offsets.

32. The method of claim 21, wherein in step (a) said Δ

Z offset is determined by computing an average Z value for said first frame and an average Z value of said second frame and computing said Δ

Z offset from said averages.

33. A method of creating a virtual three-dimensional object, comprising the steps of:

a) scanning said object in a series of scans, each scan generating a set of images;

b) converting said set of images into a set of three-dimensional frames;

c) registering said frames in each of said series of scans to each other to thereby generate a series of segments, each segment comprising a portion of a three-dimensional model of the object; and

d) registering said segments relative to each other to thereby create said virtual three-dimensional model.

34. The method of claim 33, wherein step d) comprises the steps of:

1. displaying on a monitor each of said segments,

2. prompting a user to select with a user interface device a location on each of said segments which overlaps at least one other segment;

3. storing said locations selected by said user; and

4. using said stored locations as a starting point for registering said segments relative to each other.

35. The method of claim 34, further comprising the step of displaying on said monitor the virtual three-dimensional model.

36. The method of claim 33, further comprising the step of performing a cumulative registration of all of said frames forming said virtual three-dimensional model.

37. The method of claim 34, wherein said object comprises teeth and wherein said locations selected by the user in step 2. comprise locations where virtual brackets are placed on teeth in an orthodontic treatment planning for said teeth.

38. The method of claim 37, wherein said locations are represented on said display by a graphical icon.

39. The method of claim 38, wherein said icon appears as a virtual three-dimensional object.

40. The method of claim 39, wherein said virtual three-dimensional object comprises a circular portion having a center located on the location selected by the user and direction indicating portion.

41. An orthodontic workstation performing steps b, c) and d) of the method of claim 33.

42. The method of claim 33, wherein said step of scanning is performed with a hand-held scanner.

43. A method of constructing a virtual three-dimensional model of an object using a data processing system, and at least one machine-readable memory accessible to said data processing system, comprising the steps of:

(a) obtaining a set of at least two digital three-dimensional frames of portions of the object, wherein said at least two frames comprise a set of point coordinates in a three dimensional coordinate system providing differing information of the surface of said object, whereas those frames provide a substantial overlap of the represented portions of the surface of the said object;

(b) storing data representing said set of frames in said memory; and

(c) processing said data representing said set of frames with said data processing system so as to register said frames relative to each other to thereby produce a three-dimensional virtual representation of the portion of the surface of said object covered by said set of frames, without using pre-knowledge about the spatial relationship between said frames;

said three-dimensional virtual representation being substantially consistent with all of said frames.

44. The method of claim 43, wherein said at least two digital three-dimensional frames are obtained from a CT scanner.

45. The method of claim 43, wherein said at least two digital three-dimensional frames are obtained from a Magnetic Resonance Tomography (NRT) scanner.

46. The method of claim 43, wherein said at least two digital three-dimensional frames are obtained from a processing of a at least two overlapping two-dimensional images containing three-dimensional information.

47. The method of claim 43, wherein step (c) comprises the step of performing a frame to frame registration of said set of frames, wherein each frame is registered with respect to one other frame in said set of frames.

48. The method of claim 43, wherein step (c) comprises the step of performing a cumulative registration of said set of frames, wherein at least some of said frames are registered to a plurality of other frames previously having been registered to other frames in said set of frames.

49. The method of claim 43, wherein step (c) comprises performing a frame to frame registration of said set of frames, wherein each frame is registered with respect to one other frame in said set of frames, and thereafter performing a cumulative registration of said frames wherein at least some of said frames are registered to a plurality of other frames previously having been registered to other frames in said set of frames.

50. The method of claim 43, wherein in step (c) one of said frames is a starting frame for registration, and wherein a spatial transformation relationship is derived for each of the other frames in said set of frames and stored in said memory, said spatial transformation relationship indicating how the points in said frame should be translated and rotated in a three-dimensional coordinate system to register said frames relative to said starting frame.

51. The method of claim 50, wherein said starting frame corresponds to a first frame obtained of the object.

52. The method of claim 50, wherein said frames are derived from two-dimensional images of said object, and wherein said starting frame corresponds to a selected image taken of the object and in which other images were taken of the object in the same vicinity of the object such that a substantial amount of overlap exists between said selected image and said other images.

53. The method of claim 43, wherein, in step c) said set of frames are registered to each other in a sequential order with the order determined, at least in part, upon the degree of overlap in coverage of said object in said frames.

54. The method of claim 43, said set of frames are obtained from a scanning system having a scanner and wherein said scanner comprises a hand-held scanning device and said object is scanned by moving said hand-held scanning device over said object.

55. The method of claim 43, wherein said object comprises a human.

56. The method of claim 55, wherein said object comprises teeth and associated anatomical structures.

57. The method of claim 56, wherein said object comprises a model of an anatomical structure of a human.

58. The method of claim 43, wherein said data processing system is incorporated into a work station for a scanner.

59. The method of claim 43, wherein said data processing system comprises a general purpose computer operatively connected to a scanner and said memory.

60. The method of claim 43, wherein said data processing system is coupled to a user interface including a display, and wherein data processing system is operative to display said virtual three dimensional model on said display.