Architecture for real-time 3D image registration

• US 7,280,710 B1
• Filed: 05/22/2003
• Issued: 10/09/2007
• Est. Priority Date: 05/24/2002
• Status: Expired due to Fees

• Current Assignee: Cleveland Clinic Foundation
• Original Assignee: Cleveland Clinic Foundation
• Inventors: Shekhar, Raj, Jagadeesh, Jogikal M., Castro-Pareja, Carlos R.
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): Strege; John B
• Application Number:
  US10/443,249
• Time in Patent Office: 1,601 Days
• Field of Search: 382/303, 382/304, 382/154, 382/300
• US Class Current: 382/303
• CPC Class Codes: G06T 7/35 using statistical methods
• CPC Class Codes: G06T 7/38 Registration of image sequences

Abstract

A system architecture is disclosed that facilitates rapid execution of 3D registration or alignment algorithms. A first image module (e.g., RAM) is included to store data corresponding to images to be registered. A processor coupled to the first storage module accesses the data and determined mutual histogram (MH) values which are then used to compute mutual information (MI) between the images. The processor accumulates the MH values in a second image module. The second storage module is accessible so that registered images can be displayed. The architecture is scalable facilitating distributed calculations to speed-up the registration process.

Claims

1. A hardware pipeline for 3D image registration, comprising:

a first memory module for storing volumetric data comprising a first three dimensional image;

a second memory module for storing volumetric data comprising a second three dimensional image;

a third memory module for storing MH data;

an address generator/first image controller;

an interpolator;

a second image controller; and

an accumulator/MH controller,

wherein each of the first, second and third memory modules are configured for computational access independently of the other two memory modules,

wherein the address generator/first image controller is operable to access the first memory module for first image data and mask data, and to send first image address and control data to the first memory module, and to send interpolation data and second image address data to the interpolator and second image controller, respectively, and to send first image data to the accumulator/MH controller,

wherein the second image controller is operable to receive second image data and mask data from the second memory module, and to send second image address and control data to the second memory module, and to send second image data to the accumulator/MH controller,

wherein the accumulator/MH controller is operable to send MH address and control data to the MH RAM, and to send MH data to and receives MH data from the third memory module,

wherein the interpolator is operable to send interpolation weights to the accumulator/MH controller.

2. The pipeline of claim 1, wherein at least one of:

the first and second memory modules respectively comprise one or more components of SDRAM and the third memory module comprises one or more components of synchronous fast SRAM.

3. The pipeline of claim 1, further comprising:

an address decoder; and

a compactor,

wherein the address decoder is operable to receive second image address data from the address generator, and to send cubic addresses to the second image controller, the address decoder being operable to convert the second image address data to cubic addresses which can be utilized for selective access of the second image memory module,

wherein the compactor is operable to receive interpolation weights and second image data from the interpolator and second image controller, respectively, and to send compacted second image data and weights to the accumulator/MH controller.

4. The pipeline of claim 3, wherein the interpolator comprises:

a first stage operable to calculate compliments of one or more coordinates;

a second stage operable to calculate one or more products of the one or more coordinates;

a third stage operable to perform a multiplication on one or more of the products resulting from the second stage; and

a fourth stage operable to shuffle results of the third stage to relate the results to corresponding second image values.

5. The pipeline of claim 1, where at least one of the first memory module and the second memory module are configured to organize the volumetric data according to a cubic addressing scheme.

6. The pipeline of claim 2, where at least one of the first memory module and the second memory module are configured to organize the volumetric data according to a cubic addressing scheme.

7. The pipeline of claim 3, where at least one of the first memory module and the second memory module are configured to organize the volumetric data according to a cubic addressing scheme.

8. The pipeline of claim 4, where at least one of the first memory module and the second memory module are configured to organize the volumetric data according to a cubic addressing scheme.

9. The pipeline of claim 1, wherein at least one of the address generator/first image controller, interpolator, second image controller and accumulator/MH controller comprise a field programmable gate array (FPGA).

10. The pipeline of claim 1, wherein the accumulator/MH controller clears the MH RAM at the beginning MH calculations.

11. The pipeline of claim 1, wherein the accumulator/MH controller performs interpolation such that the values added to the MH are calculated from a fractional position of the first image in the second image.

12. The pipeline of claim 11, wherein a 2×

2×

2 neighborhood of the second image can be accessed to perform interpolation.

13. The pipeline of claim 1, wherein the first image can be stored in a single 16M×

16 sequential access RAM module while the second image can be stored using a cubic addressing scheme with eight RAM modules.

14. The pipeline of claim 1, wherein the first image can be divided into a plurality of sub-volumes and distributed for calculations.

15. A method of performing 3D image registration by computing an MH matrix based on a first 3D image and a second 3D image, wherein each image is comprised of volumetric data, the method comprising:

for respective voxels in the first image;

reading voxels from the first image;

computing a transformed coordinate for the voxels by computing a vector v_Org by applying the following vector transformation;

v_Org=T·

½

(max_—

x·

(Δ

v/Δ

x)+max_—

y·

(Δ

v/Δ

x)+max_—

z·

(Δ

v/Δ

x));

verifying the validity of the transformed coordinates for the voxels; and

upon verifying the validity of the transformed coordinates, adding the interpolated values of the voxels to the MH matrix by applying the following interpolation;

$v_z=v_{\mathrm{Org}}$ $\mathrm{for}<br><br><br><br>z=0<br><br><br><br>\mathrm{to}<br><br><br><br>\mathrm{max\_z}-1$ $<br><br>v_y=v_z$ $<br><br>v_z=v_z+\mathrm{\Delta <br><br>}<br><br><br><br>v/\mathrm{\Delta <br><br>}<br><br><br><br>z$ $<br><br>\mathrm{for}<br><br><br><br>y=0<br><br><br><br>\mathrm{to}<br><br><br><br>\mathrm{max\_y}-1$ $<br><br>v_x=v_x+\left(\mathrm{\Delta <br><br>}<br><br><br><br>v/\mathrm{\Delta <br><br>}<br><br><br><br>x\right)$ $<br><br>v_B=\mathrm{Int}<br><br>\left(v_x\right)<br><br><br><br><br><br>v_{\mathrm{frac}}=v_x-v_B<br><br><br><br><br><br>W=\left[\begin{array}{c}{v}_{\mathrm{frac}}<br><br>\left(x\right)·<br><br>v_{\mathrm{frac}}<br><br>\left(y\right)·<br><br>v_{\mathrm{frac}}<br><br>\left(y\right)\\ v_{\mathrm{frac}}<br><br>\left(x\right)·<br><br>v_{\mathrm{frac}}<br><br>\left(y\right)·<br><br>\left(1-v_{\mathrm{frac}}<br><br>\left(z\right)\right)\\ v_{\mathrm{frac}}<br><br>\left(x\right)·<br><br>\left(1-v_{\mathrm{frac}}<br><br>\left(y\right)\right)·<br><br>v_{\mathrm{frac}}<br><br>\left(z\right)\\ v_{\mathrm{frac}}<br><br>\left(x\right)·<br><br>\left(1-v_{\mathrm{frac}}<br><br>\left(y\right)\right)·<br><br>\left(1-v_{\mathrm{frac}}<br><br>\left(z\right)\right)\\ \left(1-v_{\mathrm{frac}}<br><br>\left(x\right)\right)·<br><br>v_{\mathrm{frac}}<br><br>\left(y\right)·<br><br>v_{\mathrm{frac}}<br><br>\left(z\right)\\ \left(1-v_{\mathrm{frac}}<br><br>\left(x\right)\right)·<br><br>v_{\mathrm{frac}}<br><br>\left(y\right)·<br><br>\left(1-v_{\mathrm{frac}}<br><br>\left(z\right)\right)\\ \left(1-v_{\mathrm{frac}}<br><br>\left(x\right)\right)·<br><br>\left(1-v_{\mathrm{frac}}<br><br>\left(y\right)\right)·<br><br>v_{\mathrm{frac}}<br><br>\left(z\right)\\ \left(1-v_{\mathrm{frac}}<br><br>\left(x\right)\right)·<br><br>\left(1-v_{\mathrm{frac}}<br><br>\left(y\right)\right)·<br><br>\left(1-v_{\mathrm{frac}}<br><br>\left(z\right)\right)\end{array}\right]$ $<br><br>\mathrm{for}<br><br><br><br>i=0<br><br><br><br>\mathrm{to}<br><br><br><br>1$ $<br><br>\mathrm{for}<br><br><br><br>j=0<br><br><br><br>\mathrm{to}<br><br><br><br>1$ $<br><br>\mathrm{for}<br><br><br><br>k=0<br><br><br><br>\mathrm{to}<br><br><br><br>1$ $<br><br>v_{\mathrm{BAdd}}=v_B+\left[\begin{array}{c}i\\ j\\ k\end{array}\right]$ $<br><br>\mathrm{Int\_Index}=7-4<br><br>i-2<br><br>j-k$ $<br><br>\mathrm{MH}<br><br>\left(A<br><br>\left(x,y,z\right),B<br><br>\left(v_{\mathrm{BAdd}}\right)\right)+=W<br><br>\left(\mathrm{Int\_Index}\right)$

wherein the mathematical symbols used in the MH data calculation represent the following;

x, y, and z represent x, y, and z coordinates, respectively, of the voxels;

max_x, max_y, and max_z represent maximum x, y, and z dimensions, respectively, of the first image;

v_x, v_y, and v_z represent x, y, and z vectors, respectively, of the vector for computing the transformed coordinates of the voxels;

v_B represents the origin of the voxels of the second image that comprise the neighborhood of the voxels;

v_frac represents the fractional parts of v_x used to calculate interpolation weights;

W represents the vector that contains eight interpolation weights;

i, j, and k represent x, y, and z coordinates, respectively, of the voxels of the second image that comprise the neighborhood of the voxels;

Int_Index represents the W vector index used to transform respective weights of the voxels of the second image that comprise the neighborhood of the voxels; and

MH represents the Mutual Histogram matrix.