Constructing a statistical shape model from two-dimensional or three-dimensional data

• US 7,584,080 B2
• Filed: 12/06/2001
• Issued: 09/01/2009
• Est. Priority Date: 06/12/2001
• Status: Expired due to Fees

• Current Assignee: MAKO Surgical Corporation (Stryker Corporation)
• Original Assignee: Imorphics Limited (Stryker Corporation)
• Inventors: Taylor, Christopher J., Twining, Carole, Davies, Rhodri, Cootes, Timothy F.
• Primary Examiner(s): Rodriguez; Paul L
• Assistant Examiner(s): Kim; Eunhee
• Application Number:
  US10/480,445
• Publication Number:
  US 20050027492A1
• Time in Patent Office: 2,826 Days
• Field of Search: 703/2, 382/154, 382/160
• US Class Current: 703/2
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 10/471 using approximation functions
• CPC Class Codes: G06V 10/76 based on eigen-space representations, e.g. from pose or different illumination conditions; Shape manifolds
• CPC Class Codes: G06V 10/772 Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries

Abstract

A statistical shape model is built by automatically establishing correspondence between a set of two dimensional shapes or three dimensional shapes. A parameterization of each shape is determined and, a statistical shape model is built using the parameterization. An objective function is used to provide an output which indicates the quality of the statistical shape model. By performing these steps repeatedly for different parameterizations and comparing the quality of the resulting statistical shape models using output of the objective function to determine which parameterization provides the statistical shape model having the best quality, the output of the objective function is a measure of the quantity of information required to code the set of shapes using the statistical shape model.

Claims

1. A computer implemented method of building a statistical shape model by automatically establishing correspondence between a set of two-dimensional shapes or three-dimensional shapes, the method comprising:

(a) determining a parameterization of each shape, building a statistical shape model using the parameterization, using an objective function to automatically provide an output which indicates a quality of the statistical shape model, wherein the output of the objective function is a measure of the quantity of information required to code the set of shapes using the statistical shape model;

(b) performing step (a) repeatedly for different parameterizations and comparing the quality of the resulting statistical shape models using output of the objective function to automatically select a parameterization based upon said output of the objective function; and

(c) outputting the selected statistical shape model.

2. A method according to claim 1, wherein each parameterization used to perform step (a) is selected using an optimization method based upon previous parameterizations and the quality of the statistical shape models generated using those parameterizations as indicated by the output of the objective function.

3. The method according to claim 2, wherein the output of the objective function comprises a value indicative of the amount of information required to code parameters of the model, and a value indicative of the information required to code residuals for the set of shapes.

4. The method according to claim 3, wherein the output of the objective function further comprises a value indicative of the amount of information required to code mapping between parameters and the shapes.

5. The method according to claim 4 wherein for a given parameterization the objective function provides a single scalar output.

6. The method according to claim 5 wherein the single scalar output comprises a combination of the value indicative of the amount of information required to code parameters of the model, the value indicative of the information required to code residuals for the set of shapes, and the value indicative of the amount of information required to code mapping between parameters and the shapes.

7. The method according to claim 4, wherein the mapping comprises a mean vector and a covariance matrix.

8. The method according to claim 3 wherein the parameters of the model are parameter vectors, and the average amount of information per parameter vector is determined and multiplied by the number of shapes in a training set, to provide the value indicative of the amount of information required to code parameters of the model.

9. The method according to claim 3 wherein the residuals are residual vectors, and the average amount of information per residual vector is determined and multiplied by the number of shapes in the training set, to provide the value indicative of the information required to code residuals for a complete set of training shapes.

10. The method according to claim 9, wherein the number of residuals in each residual vector is twice the number of parameterizations used to generate the model.

11. The method according to claim 1, wherein the number of modes of variation of the model is selected to represent a training set to a given accuracy.

12. The method according to claim 1, wherein the boundary of each two-dimensional shape of a training set of shapes is recursively subdivided by inserting landmarks, the parameterization of the boundary being represented by the position of each landmark as a fraction of boundary path length between preceding and following landmarks.

13. The method according to claim 12, wherein the output parameterization is determined using a stochastic optimization method.

14. The method according to claim 1 wherein a set of curves is used to determine a parameterization function for the training set.

15. The method according to claim 14, wherein the set of curves is a cumulative density function.

16. The method according to claim 15, wherein the cumulative density function comprises a sum of kernel curves.

17. The method according to claim 16, wherein the cumulative density function is determined by combining increasing numbers of kernel curves to provide increasing resolution levels, and the output parameterization function is determined using the output of the objective function for each resolution level.

18. The method according to claim 16 wherein the kernel curves are Gaussian functions.

19. The method according to claim 16 wherein the kernel curves are Cauchy functions.

20. The method according to claim 16 wherein the kernel curves are two-dimensional curves.

21. The method according to claim 16 wherein the kernel curves are three-dimensional curves.

22. The method according to claim 1 wherein the boundary of each shape of the training set is parameterized by specifying a set of control landmarks used to determine a parameterization function.

23. The method according to claim 22, wherein the parameterization function is determined for increasing numbers of control landmarks to provide increasing resolution levels, and the output parameterization function is determined using the output of the objective function for each resolution level.

24. The method according to claim 22 wherein equally spaced landmarks are provided between the control landmarks.

25. The method according to claim 1, wherein the shape and grey-level appearance are both included in the model.

26. A computer implemented method of automatically parameterizing a set of three-dimensional shapes, each having a consistent topology, the method comprising automatically performing each of the following steps:

(a) mapping each three-dimensional shape to a parameterized form of the consistent topology,

(b) applying a set of landmarks to the parameterized form for a given level of resolution, each landmark being constrained to lie inside a spherical triangle formed by a triple of landmark points of a lower resolution level,

(c) upon the completion of the application of the set of landmarks for the resolution level, projecting the set of landmarks onto the three-dimensional shapes,

(d) building a statistical shape model using the set of landmarks of the resolution level,

(e) using an objective function to provide an output which indicates a quality of the statistical shape model determined using the set of landmarks of the resolution level wherein the output of the objective function is a measure of the quantity of information required to code the set of shapes using the statistical shape model;

(f) comparing the output with output determined using a different set of landmarks having the same level of resolution,

(g) repeating steps (a) to (f) to select a set of landmarks based upon said output of the objective function,

(h) repeating steps (a) to (g) at a higher level of resolution, and

(i) outputting a selected set of landmarks as parameters corresponding to said three-dimensional shapes.

27. A computer implemented method of automatically parameterizing a set of three-dimensional shapes, each having a consistent topology, the method comprising automatically performing each of the following steps:

(a) mapping each three-dimensional shape to a parameterized form of the consistent topology,

(b) applying a set of landmarks to the parameterized form,

(c) modifying the locations of the landmarks by applying a transformation,

(d) projecting the set of landmarks onto the three-dimensional shapes,

(e) building a statistical shape model using the set of landmarks,

(f) using an objective function to provide an output which indicates a quality of the statistical shape model determined using the set of landmarks, wherein the output of the objective function is a measure of the quantity of information required to code the set of shapes using the statistical shape model;

(g) comparing the output with output determined using landmarks having different locations,

(h) repeating steps (c) to (g) to determine an output set of landmarks based upon said output of the objective function, and

(i) outputting a selected set of landmarks as parameters corresponding to said three-dimensional shapes.

28. The method according to claim 27, wherein the transformation comprises, for a selected landmark, pushing other landmarks away from the selected landmark along the surface of the simple form, or pulling other landmarks towards the selected landmark along the surface of the parameterized form.

29. The method according to claim 28, wherein the transformation is defined by a wrapped kernel.

30. The method according to claim 29, wherein the wrapped kernel is a wrapped Cauchy distribution.

31. The method according to claim 29, wherein the wrapped kernel is a wrapped Gaussian distribution.

32. The method according to claim 28 wherein the parameterized form is a sphere or a torus.

33. A computer implemented method of building a statistical appearance model by automatically establishing correspondence between a set of images, the method comprising:

(a) determining a parameterization of each image, building a statistical model representing shape and appearance using the parameterization, using an objection function to automatically provide an output which indicates a quality of the statistical model, wherein the output of the objective function is a measure of the quantity of information required to code the set of images using the statistical model;

(b) performing step (a) repeatedly for different parameterizations and comparing the quality of the resulting statistical models using output of the objective function to automatically select a parameterization based upon said output of the objective function; and

(c) outputting the selected statistical model.

34. A method according to claim 33, wherein the statistical appearance model is an active appearance model.