Method and Apparatus For Accelerated Elastic Registration of Multiple Scans of Internal Properties of a Body

• US 20080317317A1
• Filed: 12/19/2006
• Published: 12/25/2008
• Est. Priority Date: 12/20/2005
• Status: Active Grant

• Current Assignee: University of Maryland Baltimore County (University of Maryland)
• Original Assignee: University of Maryland Baltimore County (University of Maryland)
• Inventors: Shekhar, Raj, Dandekar, Omkar, Castro-Pareja, Carlos
• Granted Patent: US 8,538,108 B2
• Time in Patent Office: Days
• US Class Current: 382/131
• CPC Class Codes: G06T 2207/10072 Tomographic images
• CPC Class Codes: G06T 2207/30028 Colon; Small intestine
• CPC Class Codes: G06T 2207/30052 Implant; Prosthesis
• CPC Class Codes: G06T 2207/30092 Stomach; Gastric
• CPC Class Codes: G06T 3/153 using elastic snapping
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: G06T 7/33 using feature-based methods

Abstract

Techniques for accelerated elastic registration include receiving reference scan data and floating scan data, and a first transformation for mapping coordinates of scan elements from the first scan to coordinates of scan elements in the second scan. A subset of contiguous scan elements is determined. At least one of several enhancements is implemented. In one enhancement cubic spline interpolation is nested by dimensions within a subset. In another enhancement, a local joint histogram of mutual information based on the reference scan data and the floating scan data for the subset is determined and subtracted from an overall joint histogram to determine a remainder joint histogram. Each subset is then transformed, used to compute an updated local histogram, and added to the remainder joint histogram to produce an updated joint histogram. In another enhancement, a measure of similarity other than non-normalized mutual information is derived from the updated joint histogram.

Claims

1. A method for elastic registration of multiple scans of internal properties of a body, comprising the steps of:

receiving control point transformation data that indicates a vector φ

of values for transform parameters for each control point of a plurality of control points that correspond to scan elements in a reference scan, wherein

the vector φ

of values for transform parameters for a particular control point indicates how to associate the particular control point with one or more scan elements in a floating scan different from the reference scan, and

every scan element in the reference scan has a position indicated by a plurality of coordinate values for a corresponding plurality of dimensions;

determining a plurality of subsets of contiguous scan elements in the reference scan, wherein each subset of contiguous scan elements is associated with only one control point;

determining an output vector v of values for transform parameters for each scan element in a first subset of scan elements of the reference scan, including the steps of

determining a first cubic B-spline coefficient coef1=Σ

B(w1) φ

for a first coordinate value of a scan element in the first subset a distance w1 from a control point along a first dimension of the plurality of dimensions summed over four control points, and

determining a plurality of cubic B-spline coefficients coef2=Σ

B(w2) coef1 for a corresponding plurality of coordinate values of a plurality of scan elements in the first subset a distance w2 from a control point along a different second dimension of the plurality of dimensions each summed over four control points, and

determining v based at least in part on coef2 for each scan element in the first subset; and

after determining the output vector V of values for each scan element in the first subset, then determining the output vector v of values for each scan element in a different second subset of scan elements of the reference scan,

wherein B(n) is a well known function for contributions at an arbitrary point from a control point at a normalized distance n=d/s where d is distance from the control point to the arbitrary point and s is separation of adjacent control points that straddle the arbitrary point.

2. A method as recited in claim 1, wherein the vector φ

of values for transform parameters contains values of shifts in a plurality of Cartesian dimensions.

3. A method as recited in claim 1, wherein the vector φ

of values for transform parameters includes values of rotation in a plurality of quaternion dimensions.

4. A method as recited in claim 1, said step of receiving control point transformation data further comprising receiving control point transformation data for four control points in each dimension of the reference scan for determining an initial output vector of values for transform parameters for each scan element in an initial subset of scan elements of the reference scan.

5. A method as recited in claim 3, said step of receiving control point transformation data further comprising receiving control point transformation data for fewer than four control points in each dimension of the reference scan for determining an output vector of values for transform parameters for each scan element in a subset of scan elements of the reference scan after the initial subset.

6. A method as recited in claim 1, wherein:

said step of determining the output vector v of values for transform parameters for each scan element in the first subset further comprises determining for each value of coef2 a plurality of cubic B-spline coefficients coef3=Σ

B(w3) coef2 for a corresponding plurality of coordinate values of a plurality of scan elements in the first subset a distance w3 from a control point along a different third dimension of the plurality of dimensions each summed over four control points, and

said sep of determining v based at least in part on coef2 for each scan element in the first subset further comprises determining v based at least in part on coef3.

7. A method as recited in claim 1, further comprising transforming a treatment plan for the body based at least in part on the output vector v of values for each scan element in the first subset.

8. An apparatus for elastic registration of multiple scans of internal properties of a body, comprising:

means for receiving control point transformation data that indicates a vector φ

of values for transform parameters for each control point of a plurality of control points that correspond to scan elements in a reference scan, wherein

the vector φ

of values for transform parameters for a particular control point indicates how to associate the particular control point with one or more scan elements in a floating scan different from the reference scan, and

every scan element in the reference scan has a position indicated by a plurality of coordinate values for a corresponding plurality of dimensions;

means for determining a plurality of subsets of contiguous scan elements in the reference scan, wherein each subset of contiguous scan elements is associated with only one control point;

means for determining an output vector v of values for transform parameters for each scan element in a first subset of scan elements of the reference scan, including

means for determining a first cubic B-spline coefficient coef1=Σ

B(w1) (for a first coordinate value of a scan element in the first subset a distance w1 from a control point along a first dimension of the plurality of dimensions summed over four control points, and

means for determining a plurality of cubic B-spline coefficients coef2=Σ

B(w2) coef1 for a corresponding plurality of coordinate values of a plurality of scan elements in the first subset a distance w2 from a control point along a different second dimension of the plurality of dimensions each summed over four control points, and

means for determining v based at least in part on coef2 for each scan element in the first subset; and

means for determining the output vector v of values for each scan element in a different second subset of scan elements of the reference scan after determining the output vector v of values for each scan element in the first subset,

wherein B(n) is a well known function for contributions at an arbitrary point from a control point at a normalized distance n=d/s where d is the distance from the control point to the arbitrary point and s is the separation of adjacent control points that straddle the arbitrary point.

9. An apparatus for elastic registration of multiple scans of internal properties of a body, comprising:

computer-readable memory for storing control point transformation data that indicates a vector φ

of values for transform parameters for each control point of a plurality of control points that correspond to scan elements in a reference scan, wherein

the vector φ

of values for transform parameters for a particular control point indicates how to associate the particular control point with one or more scan elements in a floating scan different from the reference scan, and

every scan element in the reference scan has a position indicated by a plurality of coordinate values for a corresponding plurality of dimensions;

a first logic circuit for determining and storing in a first register, for a first subset of contiguous scan elements in the reference scan, a first cubic B-spline coefficient coef1=B(w1) φ

for a first coordinate value of a scan element in a distance w1 from a control point along a first dimension of the plurality of dimensions summed over four control points; and

a second logic circuit for reading the first register and determining a plurality of cubic B-spline coefficients coef2=Σ

B(w2) coef1 for a corresponding plurality of coordinate values of a plurality of scan elements in the first subset a distance w2 from a control point along a different second dimension of the plurality of dimensions each summed over four control points and storing the each coef2 value in succession in a second register,

wherein

the reference scan includes a plurality of subsets of contiguous scan elements in the reference scan and each subset is associated with only one control point, and

B(n) is a well known function for contributions at an arbitrary point from a control point at a normalized distance n=d/s where d is the distance from the control point to the arbitrary point and s is the separation of adjacent control points that straddle the arbitrary point.

10. An apparatus as recited in claim 9, further comprising:

a third logic circuit for reading the second register and determining for each value of coef2 a plurality of cubic B-spline coefficients coef3=Σ

B(w3) coef2 for a corresponding plurality of coordinate values of a plurality of scan elements in the first subset a distance w3 from a control point along a different third dimension of the plurality of dimensions each summed over four control points and storing the each coef3 value in succession in a third register.

11. An apparatus as recited in claim 9, wherein at least one of the first logic circuit and the second logic circuit is a programmed field-programmable gate array (FPGA).

12. An apparatus as recited in claim 9, wherein at least one of the first logic circuit and the second logic circuit further comprises a look-up table (LUT) for values of B(n) for a plurality of values of n.

13. An apparatus as recited in claim 9, wherein the computer-readable memory is a static random access memory (SRAM).

14. An apparatus as recited in claim 9, further comprising one or more logic circuits for storing the successive values in the second register in computer-readable memory in association with each scan element in the reference scan.

15. An apparatus as recited in claim 10, further comprising one or more logic circuits for storing the successive values in the third register in computer readable memory in association with each scan element in the reference scan.

16. An apparatus as recited in claim 9, further comprising one or more logic circuits for associating one or more scan elements in the floating scan with the reference scan based at least in part on contents of the second register.

17. An apparatus as recited in claim 9, further comprising:

one or more processors; and

a computer readable-medium holding one or more sequences of instructions wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of transforming a treatment plan for the body based at least in part on the second transformation.

18. An apparatus as recited in claim 9, further comprising one or more logic circuits for determining a value for a measure of similarity between the reference scan and the floating scan based at least in part on the contents of the second register.

19. An apparatus as recited in claim 10, wherein the first logic circuit contains three field programmable gate array (FPGA) multipliers, the second logic circuit contains six FPGA multipliers and the third logic circuit contains twelve FPGA multipliers.

20-22. -22. (canceled)

23. An apparatus for elastic registration of multiple scans of internal properties of a body, comprising:

a computer-readable medium for storing;

a two dimensional first joint histogram of mutual information based on reference scan data and floating scan data for a plurality of scan elements; and

subvolume data that indicates a subset of contiguous scan elements of the plurality of scan elements,

wherein

reference scan data indicates for the plurality of scan elements a corresponding plurality of intensity values based on a first scan of the body,

floating scan data indicates for the plurality of scan elements a corresponding plurality of intensity values based on a different second scan of the body and a first transformation for mapping coordinates of scan elements from the first scan to coordinates of scan elements in the second scan, and

the joint histogram indicates a number of the plurality of scan elements that have intensity values based on the first scan in a first range of intensities and have intensity values based on the second scan in a second range of intensities;

a logic circuit for determining a local joint histogram of mutual information based on the reference scan data and the floating scan data for the subset of contiguous scan elements; and

a logic circuit for determining a remainder joint histogram of mutual information by subtracting the local joint histogram from the first joint histogram and storing the remainder joint histogram on the computer-readable medium; and

a logic circuit for determining a value for a similarity measure, based at least in part on the remainder joint histogram, for a second transformation for mapping coordinates of the subset of scan elements from the first scan to coordinates of scan elements in the second scan.

24-30. -30. (canceled)

31. An apparatus for elastic registration of multiple scans of internal properties of a body, comprising:

a computer-readable medium for storing a two dimensional joint histogram of mutual information based on reference scan data and floating scan data for a plurality of scan elements wherein

reference scan data indicates for the plurality of scan elements a corresponding plurality of intensity values based on a first scan of the body,

floating scan data indicates for the plurality of scan elements a corresponding plurality of intensity values based on a different second scan of the body and a first transformation for mapping coordinates of scan elements from the first scan to coordinates of scan elements in the second scan, and

the joint histogram indicates a number of the plurality of scan elements that have intensity values based on the first scan in a first range of intensities and have intensity values based on the second scan in a second range of intensities; and

a logic circuit for determining based on the joint histogram a measure of similarity for the reference scan data and the floating scan data, wherein the measure of similarity is not mutual information,

whereby an elastic transformation can be determined based on the measure of similarity.

32-39. -39. (canceled)

40. An apparatus for elastic registration of multiple scans of internal properties of a body, comprising:

a computer-readable medium for storing floating scan data for a plurality of scan elements comprising one Synchronized Dynamic Random Access Memory (SDRAM) dual in-line memory module (DIMM) with 64-bit addressing; and

a logic circuit for determining a joint histogram based at least in part on the floating scan data in the computer-readable medium,

whereby an elastic transformation can be determined based on the joint histogram.

41. An apparatus comprising a processor configured to perform in less time than ten minutes automatic elastic registration that maximizes a similarity measure based on substantively every scan element in a region of overlap between two scans each having 256×

256×

256 scan elements.

42. (canceled)