Method and apparatus for automatic alingment of volumetric images containing common subject matter

• US 5,946,425 A
• Filed: 06/03/1996
• Issued: 08/31/1999
• Est. Priority Date: 06/03/1996
• Status: Expired due to Term

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Sandor, Tamas, Bove, V. Michael Jr.
• Primary Examiner(s): Kelley, Christopher S.
• Assistant Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US08/657,324
• Time in Patent Office: 1,184 Days
• Field of Search: 382/131, 382/154, 382/289, 382/294, 382/128, 382/130, 364/731, 364/554, 348/580, 600/425, 600/407, 250/363.04, 345/424
• US Class Current: 382/294
• CPC Class Codes: G06T 2200/04 involving 3D image data
• CPC Class Codes: G06T 2207/10072 Tomographic images
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: G06T 7/38 Registration of image sequences

Abstract

Different tomographic images of the same subject matter are optimally related to one another through a two-step procedure whereby, first, movements are plotted on a subregion level, producing a vector map relating subregions in a first set of scan frames to subregions in another set of scan frames; and then, based on the aggregate of subregion movements, the invention characterizes the "global" displacement relating the volume represented by the first set of scan frames to that represented by the second set. More specifically, the invention generates translation and rotation vectors that describe the movements underlying shifts in subject matter from one scan to the other, and which can be applied to one frame set to align it with the other.

Claims

1. A method of aligning sets of image frames, (i) each set being representative of a volume and comprising a series of frames digitally encoding contiguous planar slices of the volume, (ii) each image frame comprising a series of image points encoded electronically as a grid of pixels, and (iii) the sets including redundant volumetric subject matter, the method comprising the steps of

a. automatically identifying common volumetric subject matter on a subregion level by systematically comparing pixels representing a subregion of a selected frame of a first frame set to pixels representing subregions of a plurality of frames of the second frame set in order to identify correspondences between subregions of the first frame set and subregions of the second frame set;

b. defining a field of three-dimensional translation vectors mapping each of a plurality of the first-set subregions to corresponding second-set subregions with the smallest mapping error;

c. deriving, from the translation vectors, a set of global vectors specifying translation and rotation between the common volumetric subject matter; and

d. based on the global vectors, translating and rotating the first frame set such that the common volumetric subject matter encoded by the frame sets is aligned.

2. The method of claim 1 wherein the global vectors are derived according to steps comprising:

a. utilizing the translation vectors to generate a single rotation vector maximally consistent with the mapping vectors and relating the first volume to the second volume;

b. utilizing the mapping vectors to generate a single translation vector maximally consistent with the mapping vectors and relating the first volume to the second volume,

the rotation and translation vectors encoding spatial displacement between the first and second volumes.

3. The method of claim 2 wherein the single rotation vector and the single translation vector are generated by a least-squares fit.

4. The method of claim 1 further comprising the step of preprocessing each set of frames to reduce high-frequency noise and to select for anatomical features of a predetermined size range.

5. The method of claim 4 wherein the preprocessing step comprises filtering with the Laplacian of a Gaussian.

6. A method of aligning sets of image frames, (i) each set being representative of a volume and comprising a series of frames digitally encoding contiguous planar slices of the volume, (ii) each image frame being represented as a pixelmap image datafile comprising a grid of pixels, and (iii) the sets including common volumetric subject matter, the method comprising the steps of:

a. defining, in a first frame of a first set, a search block comprising a plural number of pixels;

b. defining, at identical locations in each of a plurality of frames of a second set, a target window comprising a plural number of pixels at least as large as the number of pixels in the search block;

c. searching for common volumetric subject matter by comparing the pixels of the search block with the pixels of each of the target windows and deriving an error factor representative of image differences therebetween;

d. identifying common volumetric subject matter by selecting the target-window pixels associated with the smallest error factor;

e. defining a three-dimensional translation vector mapping the search block to the selected target-window pixels;

f. defining, in the first frame of the first set, a new search block comprising a group of pixels offset with respect to the previous search block;

g. repeating steps (b) through (e);

h. completing the search for common volumetric subject matter by repeating steps (f) and (g) until all of the pixels of the first frame of the first set have been defined in a search block;

i. deriving, from the translation vectors, a set of global vectors specifying translation and rotation between the common volumetric subject matter; and

j. based on the global vectors, aligning the first frame set with the second frame set.

7. The method of claim 6 wherein the subject matter comprises features each having a size, the target window being larger than the size of the smallest feature.

8. The method of claim 6 wherein the search block has 256 pixels and the target windows each have 2304 pixels.

9. The method of claim 6 wherein the global vectors are derived according to steps comprising:

a. utilizing the translation vectors to generate a single rotation vector maximally consistent with the mapping vectors and relating the first volume to the second volume;

b. utilizing the mapping vectors to generate a single translation vector maximally consistent with the mapping vectors and relating the first volume to the second volume,

the rotation and translation vectors encoding spatial displacement between the first and second volumes.

10. The method of claim 6 further comprising the step of preprocessing each set of frames to reduce high-frequency noise and to select for anatomical features of a predetermined size range.

11. The method of claim 10 wherein the preprocessing step comprises filtering with the Laplacian of a Gaussian.

12. The method of claim 6 wherein the new search window is offset with respect to the previous search window so as to be adjacent thereto.

18. The method of claim 6 wherein the new search window is offset with respect to the previous search window to overlap therewith.

13. Apparatus for aligning first and second sets of digitized image frames, each set being representative of a volume and comprising a series of frames digitally encoding contiguous planar slices of the volume, the sets including common volumetric subject matter, said apparatus comprising:

a. a first set of memory buffers for storing the first set of digitized frames;

b. a second set of memory buffers for storing the second set of digitized frames;

c. analysis means configured to;

i. identify common volumetric subject matter by systematically comparing groups of pixels from a selected frame of the first frame set to groups of pixels of a plurality of frames of the second frame set;

ii. define a field of three-directional translation vectors mapping each of a plurality of pixel groups of the first frame set to corresponding pixel groups of the second frame set with the smallest mapping error;

iii. derive, from the translation vectors, a set of global vectors specifying translation and rotation between the volumes; and

iv. align, based on the global vectors, the pixels of the first frame set with the pixels of the second frame set such that the volumes encoded by the frame sets are aligned.

14. The apparatus of claim 13 wherein the analysis means is further configured to preprocess each set of frames to reduce high-frequency noise and to select for anatomical features of a predetermined size range.

15. Apparatus for aligning first and second sets of digitized image frames, each set being representative of a volume and comprising a series of frames digitally encoding contiguous planar slices of the volume, the sets including common volumetric subject matter, said apparatus comprising:

a. a computer memory comprising a first set of memory buffers for storing the first set of digitized frames and a second set of memory buffers for storing the second set of digitized frames;

b. analysis means configured to;

i. define, in a first memory buffer of the first set, a search block comprising a plural number of pixels;

ii. define, at identical locations in each of a plurality of memory buffers of the second set, a target window comprising a plural number of pixels at least as large as the number of pixels in the search block;

iii. search for common volumetric subject matter by comparing the pixels of the search block with the pixels of each of the target windows;

iv. derive an error factor representative of image differences therebetween;

v. identify common volumetric subject matter by selecting the target-window pixels associated with the smallest error factor;

vi. define and store, in the computer memory, a three-dimensional translation vector mapping the search block to the selected target-window pixels;

vii. define, in the first frame of the first set, a new search block comprising a group of pixels offset with respect to the previous search block;

viii. repeat (ii) through (vi);

ix. complete the search for common volumetric subject matter by repeating (vii) and (viii) until all of the pixels of the first frame of the first set have been defined in a search block;

xii. derive, from the translation vectors, a set of global vectors specifying translation and rotation between the common volumetric subject matter and store the global vectors in the computer memory; and

xiii. based on the global vectors, align the first frame set with the second frame set.

16. The apparatus of claim 15 wherein the subject matter comprises features each having a size, the target window being larger than the size of the smallest feature.

17. The apparatus of claim 15 wherein the search block has 256 pixels and the target windows each have 2304 pixels.