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

• US 7,027,642 B2
• Filed: 04/13/2001
• Issued: 04/11/2006
• Est. Priority Date: 04/28/2000
• Status: Expired due to Term

• Current Assignee: Orametrix Incorporated
• Original Assignee: Orametrix Incorporated
• Inventors: Weise, Thomas, Imgrund, Hans, Rubbert, Rüdger, Sporbert, Peer, Kouzian, Dimitrij
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): CARTER, AARON W
• Application Number:
  US09/835,007
• Publication Number:
  US 20020006217A1
• Time in Patent Office: 1,824 Days
• Field of Search: 382/154, 382/285, 345419-427, 356 12- 14, 348 42- 60, 359462-477, 352 57- 65, 33/204, 353 7- 9, 378 41- 42, 396324-331
• US Class Current: 382/154
• 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 the data processing system. A set of at least two digital three-dimensional frames of portions of the object are obtained from a scanner or other source comprising 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. Data representing the set of frames are stored in the memory and processed by the 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 the set of 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 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 X, Y, and Z 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 using a frame to frame registration process to thereby produce a three-dimensional virtual model of the object substantially consistent with all of said frames;

said frame to frame registration process comprising the steps of;

(i) performing an initialization step comprising the sub-steps of;

(A) selecting one of the frames from said set of frames as the first frame;

(B) ordering said set of frames in a sequence of frames Frame_i for i=1 to N for further processing, wherein Frame₁ is the first frame;

(C) setting a quality index for evaluating the quality of the overall registration of one frame to another frame;

(D) setting the frame subscript value i=2; and

(E) selecting Frame<sub>i−

1</sub> and Frame_i for registering Frame_i to Frame<sub>i−

1</sub>;

(ii) transforming the Z coordinate of every point in Frame_i, thereby bringing Frame_i closer to Frame<sub>i−

1</sub>, comprising the sub-steps of;

(A) calculating for Frame<sub>i−

1</sub>;

(1) the sum of all Z coordinates Z<sub>sum i−

1</sub>=sum of the Z coordinate of every point in Frame<sub>i−

1</sub>; and

(2) the median Z coordinate Z<sub>median i−

1</sub>=Z<sub>sum i−

1</sub> divided by the number of points in Frame<sub>i−

1</sub>;

(B) calculating for Frame_i;

(1) the sum of all Z coordinates Z_{sum i}=sum of the Z coordinate of every point in Frame_i; and

(2) the median Z coordinate Z_{median i}=Z_{sum i} divided by the number of points in Frame_i; and

(C) calculating Δ

Z=Z_{median i}−

Z<sub>median i−

1</sub>;

subtracting Δ

Z from the Z coordinate of every point in Frame_i, thereby transforming the Z coordinate of every point in Frame_i, and setting Frame_i=Frame_i having the transformed Z coordinates.

(iii) calculating the translation matrix for Frame_i comprising the sub-steps of;

(A) calculating a minimum distance vector from every point in Frame_i to the surface of Frame<sub>i−

1</sub>, thereby creating a set of minimum distance vectors for Frame_i;

(B) eliminating from said set of minimum distance vectors for Frame_i each of said set of minimum distance vector for Frame_i that satisfies one or more exclusion criteria from a set of exclusion criteria, thereby creating a remaining set of minimum distance vectors for Frame_i, and marking each of the points corresponding to the remaining set of minimum distance vectors for Frame_i as an overlapping point, wherein said overlapping points define the area of overlap between Frame<sub>i−

1</sub> and Frame_i;

(C) calculating a vector sum of minimum distance vectors for Frame_i by summing all minimum distance vectors corresponding to said overlapping points in Frame_i; and

(D) calculating a median minimal distance vector (t)_i for Frame_i by dividing the vector sum of minimum distance vectors for Frame_i with the number of vectors corresponding to said overlapping points in Frame_i thereby the median minimal distance vector (t)_i for Frame_i forming the translation matrix [T](t)_i;

(iv) calculating the rotation transformation matrix for Frame_i comprising the sub-steps of;

A creating a copy of Frame_i, and designating said copy of Frame_i Frame_i*;

(B) subtracting the median minimal distance vector (t)_i from every point in Frame_i*;

(C) getting a position vector for every overlapping point in Frame_i* extending from the origin of the coordinate system for Frame_i* to the overlapping point in Frame_i*;

(D) calculating a vector sum of all position vectors corresponding to all of the overlapping points in Frame_i*;

(E) calculating the center of mass for Frame_i* by dividing the vector sum of all position vectors corresponding to all of the overlapping points in Frame_i* with the number of said position vectors corresponding to all of said overlapping points in Frame_i*;

(F) calculating a cross-vector for every overlapping point in Frame_i* by performing a cross-product operation of (1) the position vector for the overlapping point in Frame_i* substracted by the vector of the center of mass for Frame_i* and (2) said minimum distance vector for the overlapping point in Frame_i*;

(G) calculating a sum of all the cross-vectors corresponding to all of the overlapping points in Frame_i*;

(H) applying a weighting factor to the sum of all of said cross-vectors for Frame_i* thereby producing a weighted sum of all the cross-vectors for Frame_i*; and

(I) scaling the weighted sum of all the cross-vectors for Frame_i* with an empirical acceleration factor f thereby creating a scaled weighted sum of all the cross-vectors for Frame_i* thereby said scaled weighted sum of all the cross-vectors for Frame_i* forming the rotation transformation matrix [T](R)_i,

(v) applying the transformation to Frame_i and evaluating the results comprising the sub-steps of;

(A) computing the transformation matrix for Frame_i [T]_i=+[T](t)_i+[T](R)_i; and

applying the transformation matrix [T]_i to every point in Frame_i thereby producing a transformed Frame_i wherein [T](t)_i produces the transalation of the X, Y and Z coordinates of every point in Frame_i and [T](R)_i produces the magnitude and direction of rotation of Frame_i;

(B) calculating the closeness factor of the transformed Frame_i and Frame<sub>i−

1</sub> and comparing said closeness factor with the quality index;

(C) if the closeness factor>

the quality index, then returning to step (iii);

otherwise proceeding to the next step;

(D) if i<

N, setting i=i+1 and returning to step (ii) until Frame_N is registered.

2. The method of claim 1, wherein step (d) further comprises the step of performing a cumulative registration of said set of frames.

3. The method of claim 1, wherein in step (d)(i) after selecting said starting frame for registration, 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.

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

5. The method of claim 1, 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.

6. The method of claim 1, wherein, in step (d), said sequential order is determined, at least in part, upon the degree of overlap in coverage of said object in said frames.

7. 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.

8. The method of claim 7, wherein said object comprises a human.

9. The method of claim 8, wherein said object comprises teeth and associated anatomical structures.

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

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

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

13. 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).

14. The method of claim 13, 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.

15. The method of claim 14, 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.

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

17. 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.

18. 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 using a frame to frame registration process to thereby generate a series of segments, each segment comprising a portion of a three-dimensional model of the object;

said frame to frame registration process comprising the steps of;

(i) performing an initialization step comprising the sub-steps of;

(A) selecting one of the frames from said set of frames as the first frame;

(B) ordering said set of frames in a sequence of frames Frame_i for i=1 to N for further processing, wherein Frame_i is the first frame;

(C) setting a quality index for evaluating the quality of the overall registration of one frame to another frame;

(D) setting the frame subscript value i=2; and

(E) selecting Frame<sub>i−

1</sub> and Frame_i for registering Frame_i to Frame<sub>i−

1</sub>;

(ii) transforming the Z coordinate of every point in Frame_i, thereby bringing Frame_i closer to Frame<sub>i−

1</sub>, comprising the sub-steps of;

(A) calculating for Frame<sub>i−

1</sub>;

(1) the sum of all Z coordinates Z<sub>sum i−

1</sub>=sum of the Z coordinate of every point in Frame<sub>i−

1</sub>; and

(2) the median Z coordinate Z<sub>median i−

1</sub>=Z<sub>sum i−

1</sub> divided by the number of points in Frame<sub>i−

1</sub>;

(B) calculating for Frame_i;

(1) the sum of all Z coordinates Z_{sum i}=sum of the Z coordinate of every point in Frame_i; and

(2) the median Z coordinate Z_{median i}=Z_{sum i} divided by the number of points in Frame_i; and

(C) calculating Δ

Z=Z_{median i}−

Z<sub>median i−

1</sub>;

subtracting Δ

Z from the Z coordinate of every point in Frame_i, thereby transforming the Z coordinate of every point in Frame_i, and setting Frame_i=Frame_i having the transformed Z coordinates.

(iii) calculating the translation matrix for Frame_i comprising the sub-steps of;

(A) calculating a minimum distance vector from every point in Frame_i to the surface of Frame<sub>i−

1</sub>, thereby creating a set of minimum distance vectors for Frame_i;

(B) eliminating from said set of minimum distance vectors for Frame_i each of said set of minimum distance vector for Frame_i that satisfies one or more exclusion criteria from a set of exclusion criteria, thereby creating a remaining set of minimum distance vectors for Frame_i, and marking each of the points corresponding to the remaining set of minimum distance vectors for Frame_i as an overlapping point, wherein said overlapping points define the area of overlap between Frame<sub>i−

1</sub> and Frame_i;

(C) calculating a vector sum of minimum distance vectors for Frame_i by summing all minimum distance vectors corresponding to said overlapping points in Frame_i; and

(D) calculating a median minimal distance vector (t)_i for Frame_i by dividing the vector sum of minimum distance vectors for Frame_i with the number of vectors corresponding to said overlapping points in Frame_i thereby the median minimal distance vector (t)_i for Frame_i forming the translation matrix [T](t)_i;

(iv) calculating the rotation transformation matrix for Frame_i comprising the sub-steps of;

(A) creating a copy of Frame_i, and designating said copy of Frame_i Frame_i*;

(B) subtracting the median minimal distance vector (t)_i from every point in Frame_i*;

(C) getting a position vector for every overlapping point in Frame_i* extending from the origin of the coordinate system for Frame_i* to the overlapping point in Frame_i*;

(D) calculating a vector sum of all position vectors corresponding to all of the overlapping points in Frame_i*;

(E) calculating the center of mass for Frame_i* by dividing the vector sum of all position vectors corresponding to all of the overlapping points in Frame_i* with the number of said position vectors corresponding to all of said overlapping points in Frame_i*;

(F) calculating a cross-vector for every overlapping point in Frame_i* by performing a cross-product operation of (1) the position vector for the overlapping point in Frame_i* substracted by the vector of the center of mass for Frame_i* and (2) said minimum distance vector for the overlapping point in Frame_i*;

(G) calculating a sum of all the cross-vectors corresponding to all of the overlapping points in Frame_i*;

(H) applying a weighting factor to the sum of all of said cross-vectors for Frame_i* thereby producing a weighted sum of all the cross-vectors for Frame_i*; and

(I) scaling the weighted sum of all the cross-vectors for Frame_i* with an empirical acceleration factor f thereby creating a scaled weighted sum of all the cross-vectors for Frame_i* thereby said scaled weighted sum of all the cross-vectors for Frame_i* forming the rotation transformation matrix [T](R)_i,

(v) applying the transformation to Frame_i and evaluating the results comprising the sub-steps of;

(A) computing the transformation matrix for Frame_i [T]_i=+[T](t)_i+[T](R)_i; and

applying the transformation matrix [T]_i to every point in Frame_i thereby producing a transformed Frame, wherein [T](t)_i produces the transalation of the X, Y and Z coordinates of every point in Frame_i and [T](R)_i produces the magnitude and direction of rotation of Frame_i;

(B) calculating the closeness factor of the transformed Frame_i and Frame<sub>i−

1</sub> and comparing said closeness factor with the quality index;

(C) if the closeness factor<

the quality index, then returning to step (iii);

otherwise proceeding to the next step;

(D) if i>

N, setting i=i+1 and returning to step (ii) until Frame_N is registered;

and

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

19. The method of claim 18, 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.

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

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

22. The method of claim 19, 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.

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

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

25. The method of claim 24, 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.

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

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

28. 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 using a frame to frame registration process 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;

said frame to frame registration process comprising the steps of;

(i) performing an initialization step comprising the sub-steps of;

(A) selecting one of the frames from said set of frames as the first frame;

(B) ordering said set of frames in a sequence of frames Frame_i for i=1 to N for further processing, wherein Frame_i is the first frame;

(C) setting a quality index for evaluating the quality of the overall registration of one frame to another frame;

(D) setting the frame subscript value i=2; and

(E) selecting Frame<sub>i−

1</sub>and Frame_i for registering Frame_i to Frame<sub>i−

1</sub>;

(ii) transforming the Z coordinate of every point in Frame_i, thereby bringing Frame_i closer to Frame<sub>i−

1</sub>, comprising the sub-steps of;

(A) calculating for Frame<sub>i−

1</sub>;

(1) the sum of all Z coordinates Z<sub>sum i−

1</sub>=sum of the Z coordinate of every point in Frame<sub>i−

1</sub>; and

(2) the median Z coordinate Z<sub>median i−

1</sub>=Z<sub>sum i−

1</sub> divided by the number of points in Frame<sub>i−

1</sub>;

(B) calculating for Frame_i;

(1) the sum of all Z coordinates Z_{sum i}=sum of the Z coordinate of every point in Frame_i; and

(2) the median Z coordinate Z_{median i}=Z_{sum i} divided by the number of points in Frame_i; and

(C) calculating Δ

Z=Z_{median i}−

Z<sub>median i−

1</sub>;

subtracting Δ

Z from the Z coordinate of every point in Frame_i, thereby transforming the Z coordinate of every point in Frame_i, and setting Frame_i=Frame_i having the transformed Z coordinates,

(iii) calculating the translation matrix for Frame_i comprising the sub-steps of;

(A) calculating a minimum distance vector from every point in Frame_i to the surface of Frame<sub>i−

1</sub>, thereby creating a set of minimum distance vectors for Frame_i;

(B) eliminating from said set of minimum distance vectors for Frame_i each of said set of minimum distance vector for Frame_i that satisfies one or more exclusion criteria from a set of exclusion criteria, thereby creating a remaining set of minimum distance vectors for Frame_i, and marking each of the points corresponding to the remaining set of minimum distance vectors for Frame_i as an overlapping point, wherein said overlapping points define the area of overlap between Frame<sub>i−

1</sub> and Frame_i;

(C) calculating a vector sum of minimum distance vectors for Frame_i by summing all minimum distance vectors corresponding to said overlapping points in Frame_i; and

(D) calculating a median minimal distance vector (t)_i for Frame_i by dividing the vector sum of minimum distance vectors for Frame_i with the number of vectors corresponding to said overlapping points in Frame_i thereby the median minimal distance vector (t)_i for Frame_i forming the translation matrix [T](t)_i;

(iv) calculating the rotation transformation matrix for Frame_i comprising the sub-steps of;

(A) creating a copy of Frame_i, and designating said copy of Frame_i Frame_i*;

(B) subtracting the median minimal distance vector (t)_i from every point in Frame_i*;

(C) getting a position vector for every overlapping point in Frame_i* extending from the origin of the coordinate system for Frame_i* to the overlapping point in Frame_i*;

(D) calculating a vector sum of all position vectors corresponding to all of the overlapping points in Frame_i*;

(E) calculating the center of mass for Frame_i* by dividing the vector sum of all position vectors corresponding to all of the overlapping points in Frame_i* with the number of said position vectors corresponding to all of said overlapping points in Frame_i*;

(F) calculating a cross-vector for every overlapping point in Frame_i* by performing a cross-product operation of (1) the position vector for the overlapping point in Frame_i* substracted by the vector of the center of mass for Frame_i* and (2) said minimum distance vector for the overlapping point in Frame_i*;

(G) calculating a sum of all the cross-vectors corresponding to all of the overlapping points in Frame_i*;

(H) applying a weighting factor to the sum of all of said cross-vectors for Frame_i* thereby producing a weighted sum of all the cross-vectors for Frame_i*; and

(I) scaling the weighted sum of all the cross-vectors for Frame_i* with an empirical acceleration factor f thereby creating a scaled weighted sum of all the cross-vectors for Frame_i* thereby said scaled weighted sum of all the cross-vectors for Frame_i* forming the rotation transformation matrix [T](R)_i;

(v) applying the transformation to Frame_i and evaluating the results comprising the sub-steps of;

(A) computing the transformation matrix for Frame_i [T]_i=+[T](t)_i+[T](R)_i; and

applying the transformation matrix [T]_i to every point in Frame_i thereby producing a transformed Frame_i wherein [T](t)_i produces the transalation of the X, Y and Z coordinates of every point in Frame_i and [T](R)_i produces the magnitude and direction of rotation of Frame_i;

(B) calculating the closeness factor of the transformed Frame_i and Frame<sub>i−

1</sub> and comparing said closeness factor with the quality index;

(C) if the closeness factor<

the quality index, then returning to step (iii);

otherwise proceeding to the next step;

(D) if i<

N, setting i=i+1 and returning to step (ii) until Frame_N is registered.

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

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

31. The method of claim 28, 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.

32. The method of claim 28, wherein step (c) further comprises the step of performing a cumulative registration of said set of frames.

33. The method of claim 28, wherein in step (c)(i) after selecting said starting frame for registration, 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.

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

35. The method of claim 28, 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.

36. The method of claim 28, wherein, in step c) said sequential order is determined, at least in part, upon the degree of overlap in coverage of said object in said frames.

37. The method of claim 28, 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.

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

39. The method of claim 38, wherein said object comprises teeth and associated anatomical structures.

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

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

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

43. The method of claim 28, 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.