Field of the Invention

This invention relates to image registration and more particularly to registering a 2D image with the corresponding slice of a 3D volume.

Background of the Invention

Any discussion of the prior art throughout the specification should in no way be considered as an admission that such prior art is widely known or forms part of common general knowledge in the field.

Image registration of 2D images and 3D volumes has many industrial and medical applications. Industrial applications include grain structure analysis and data fusion for fault detection. Available methods for 2D-3D image registration can be categorized into two groups, namely global optimization based registration and point feature-based registration. Presently available registration techniques for the registration of a Mega-pixel 2D image to a Giga-voxel 3D volume require many hundreds of CPU hours utilizing state of the art CPU technology. Major drawbacks of global optimization are the flatness of the similarity measure maxima (caused by self similarity of images) and high computational complexity. Global techniques are still not as easily parallelizable like point feature-based techniques. In addition, global registration techniques suffer from a local maxima problem. On the other hand, feature-based methods are not suitable for high accuracy registration as feature misregistration can perturb the estimated model. Further, the accuracy of existing methods for 2D-3D feature matching is quite low as existing descriptors do not account for 2D-3D transformations.

It is an object of the present invention to overcome or ameliorate at least one of the disadvantages of the prior art, or to provide a useful alternative.

What is generally desirable is a hybrid approach considering the speed- accuracy trade off. First a rough registration has to be done at the global scale and then the optimization has to be done locally. The feature descriptors should be matched using a proper imaging model.

Accordingly, the invention relates generally to a repeatable keypoint detection methodology for 2D images and 3D volumes, to present a novel way of descriptor formation for matching 2D keypoints and 3D keypoints and to model 2D to 3D transformations for registration up to an affinity under low feature matching accuracy.

Other advantages of the invention will in part be obvious and will in part be apparent from the specification and drawings.

Unless the context clearly requires otherwise, throughout the description and the claims, the words "comprise", "comprising", and the like are to be construed in an inclusive sense as opposed to an exclusive or exhaustive sense; that is to say, in the sense of "including, but not limited to".

Although the invention will be described with reference to specific examples it will be appreciated by those skilled in the art that the invention may be embodied in many other forms.

Summary of the Invention

According to a first aspect of the present invention there is provided a method for identifying the placement and orientation of a 2D image produced from a slice of a 3D volume, the method comprising the following steps:

a) from the 2D image, selecting 2D image features and computing feature descriptors from them;

b) finding 3D volume features in the 3D volume;

c) for a set of planes with different orientations through each 3D feature computing 2D descriptors centered on said 3D feature, one descriptor for each plane through each 3D feature;

d) finding matches between the descriptors for the 2D image features and the descriptors for the 3D volume features; and

e) determining a model for the position and orientation of the 2D image with respect to the slice, which is compatible with a plurality of matched 2D and 3D features.

In an embodiment, a model is computed from a small number of 2D-3D feature matches and is used to guide the matching of further features. In another embodiment, the model is computed from one 2D-3D match. In yet another embodiment, the model is computed from two 2D-3D matches.

In another embodiment, the method of guiding the match of further features is to consider only further matches that are consistent with the model as regards some or all the following properties:

a) only 3D features in planes similar to that defined by the model are considered;

b) only 2D-3D matches whose distances one from another are compatible with a fixed scale of 2D slice and 3D volume are considered; c) only 2D-3D matches whose position is compatible with the transformation model are considered.

According to a second aspect of the present invention there is provided a method of identifying scale invariant features of a 3D volume defined by a plurality of voxels, the method comprising: locating voxel amplitude extrema in a plurality of filtered volumes produced from said image by:

a) comparing the amplitude of each voxel in a filtered volume under consideration with the amplitudes of surrounding voxels to identify local maximum and minimum voxels;

b) comparing amplitudes of said local maximum and minimum voxels with the amplitudes of the voxels of a predecessor filtered volume to identify maximum and minimum voxels;

c) comparing the amplitudes of said local maximum and minimum voxels with the amplitudes of voxels of a successor filtered volume to identify actual maximum and minimum voxels; and

d) producing subregion volume descriptors for said voxel extremum. In an embodiment, the method comprises producing said filtered volumes. In another embodiment, producing a filtered volume comprises subtracting two blurred volumes derived from the initial volume, to produce a difference volume.

In yet another embodiment, producing a plurality of difference volumes comprises producing a plurality of blurred volumes from the initial volume and subtracting each blurred volume from a blurred volume produced previously as recited in claim 8 of the appended claims.

In still another embodiment, producing subregion volume descriptors for a voxel extremum further comprises producing a plurality of 2D descriptors, associated with a set of planes within a subregion around each voxel. Preferably, producing a plurality of 2D descriptors associated with a set of planes further comprises selecting a set of planes through a 3D keypoint with different orientations and selecting a 2D keypoint descriptor for each plane.

According to a third aspect of the present invention there is provided an apparatus for computing scale invariant features of a volume defined by a plurality of voxels, the apparatus comprising a processor circuit configured to locate voxel extrema in a plurality of filtered volumes by:

a) comparing the amplitude of each voxel in a filtered volume under consideration with the amplitudes of surrounding voxels to identify local maximum and minimum voxels

b) comparing amplitudes of said local maximum and minimum voxels with the amplitudes of the voxels of a predecessor filtered volume to identify maximum and minimum voxels and

c) comparing the amplitudes of said local maximum and minimum voxels with the amplitudes of with the voxels of a successor filtered volumes to identify actual maximum and minimum voxels and

d) producing subregion volume descriptors for said actual voxel extrema.

In an embodiment, said processor circuit is configured to produce said filtered volumes. In another embodiment, in order to produce a filtered volume, said processor circuit is configured to compute two blurred volumes from the initial volume and to subtract them to produce a difference volume.

In another embodiment, the processor circuit is configured to successively blur and subtract as recited in claim 14 of the appended claims and is configured to use a blurred volume produced in a preceding blurring function as said original volume in successive blurring functions.

According to a fourth aspect of the present invention there is provided a method for matching 2D features of an image defined by a plurality of pixels and 3D features of a volume defined by a plurality of voxels, the method comprising:

a) selecting a 2D descriptor for each 2D feature of said image; b) selecting a set of 2D descriptors from planes recited in claim 10 of the appended claims for said 3D feature;

c) comparing each image 2D feature descriptor with the set of descriptors belonging to each 3D feature; and

d) evaluating matched 2D-3D features with respect to a transformation model for outlier rejection.

In an embodiment, a single 2D-3D correspondence is selected at a time, and used to guide the selection of further correspondences, consistent with the plurality of compatible transformation models.

In another embodiment, 2D image features are matched with descriptors belonging to 3D features in a way that different 2D image descriptors are matched with the 3D features associated with planes with similar orientation.

In still another embodiment, the method of matching 2D features comprises the following steps.

a) at one time, matching 2D image descriptors only with descriptors derived from planes of one orientation through 3D keypoint features, and computing a transformation model;

b) at a sequence of times in this way, matching the 2D image descriptors with features derived from planes of all selected orientations and selecting the best model based on inlier score.

In another embodiment, the method further comprises producing the best model under low feature matching accuracy. In another embodiment, the

transformation model is computed from 2D-3D correspondences, and specifies a hypothesized position of the 2D image with respect to the 3D volume.

In yet another embodiment, the method comprises producing the

transformation model by selecting 3 2D-3D correspondences each time successively until the best model is found.

According to a fifth aspect of the present invention there is provided an apparatus for matching of 3D features of a volume defined by a plurality of voxels with 2D features of an image defined by a plurality of pixels, the apparatus comprising a processor circuit configured to:

a) selecting a set of 2D descriptors on each plane recited in claim 10 of the appended claims for said 3D feature to solve the scaling ambiguity between 2D and 3D features;

b) comparing each 2D feature descriptor with the set of descriptors belong to each 3D feature; and

c) evaluating matched 2D-3D features with respect to a transformation model for outlier rejection.

In an embodiment, said processor circuit is configured to produce said scale invariant 2D features for each plane. In another embodiment, said processor circuit is configured to evaluate the transformation model by selecting 3 2D-3D

correspondences each time successively until the best model is found.

According to a sixth aspect of the present invention there is provided a method for outlier rejection of matches, the method comprising the steps of:

a) selecting 1 or 3 point correspondences for model generation;

b) computing a best model through RANSAC based model selection; and

c) rejecting outliers that do not conform to the selected model.

In an embodiment, the method comprises producing the mapping model. In an embodiment, producing the mapping model comprises performing registration.

According to a seventh aspect of the present invention there is provided an apparatus for outlier rejection of matches, the method comprising:

a) selecting 1 or 3 point correspondences for model generation;

b) RANSAC based model selection; and

c) rejecting outliers based on the selected model.

In a preferred embodiment, said processor circuit is configured for producing the mapping model.

The present invention addresses one or more of the deficiencies identified in the prior art through novel techniques for repeatable keypoint detection for 2D images and 3D volumes, a novel way of descriptor formation for matching 2D keypoints and 3D keypoints and model estimation for registration up to an affinity under low feature matching accuracy. We further develop techniques for model estimation. We present an affine registration estimation method based on an algorithm that requires three true positive matches of feature points and extend this to estimate the model based on only a single true positive match, which we call the one-point algorithm. The algorithm is based on Branch-and-Bound for rigid model estimation with guaranteed convergence. In addition, handling image scale is also addressed by resolving the ambiguity of 2D image scale and 3D image scale by showing that the 2D scale and the 3D scale do not represent similar image and volume neighborhoods. Furthermore, we introduce a novel feature descriptor based on image curvature founded on mathematically sound principles for improving feature matching accuracy. We indicate that the 2D-3D registration accuracy improves under this novel feature descriptor.

This invention uses the Difference of Gaussian (DoG) as our detector measure for detecting repeatable keypoints among 2D-3D images. For 3D volumes we extend the DoG approach with a 3D Gaussian kernel. The scale-space of 3D volumes is generated using its Laplacian approximation obtained as the difference of adjacent volumes in the scale-space.

Having produced the keypoints in both spaces, the method and the apparatus may further involve generating descriptors for keypoints. A 3D keypoint descriptor cannot be directly matched with a 2D keypoint descriptor, so the apparatus hypothesizes that a descriptor computed on a patch around a 2D keypoint and a 2D descriptor computed on a plane passing through the 3D keypoint with sufficiently close orientation to the 2D keypoint patch should produce a matchable descriptor if the two keypoints are correspondences. Sampling planes through a 3D keypoint to approximate all possible orientations produces matchable descriptors with the 2D image. Thus, for the 3D case, descriptors are generated by sampling planes through each 3D keypoint using bilinear or higher-order interpolation. In this way, one 3D keypoint has many descriptors.

To improve the matching accuracy of generated features, the scaling ambiguity between 2D and 3D features has to be resolved. The scale of a 3D keypoint is not equivalent to the scale of a 2D keypoint for computing descriptors, as shown later in this document.

For outlier rejection, the apparatus uses a novel image model. This is done by representing any plane in R ³ by a normal vector and a point on the plane. By selecting a coordinate frame corresponding oriented with the normal vector, a point on the 2D plane can be related with the corresponding plane in the 3D space via an affine transformation as described later in this document.

The invention accordingly comprises several steps, and the relation of one or more of such steps with each of the others, and the apparatus embodying features of construction, combinations of elements and arrangement of parts that are adapted to affect such steps, is exemplified in the following detailed disclosure, and the scope of the invention will be indicated in the claims.

Definition

For the sake of clarity throughout the description and claims, the "overbar" designation appears to the right of the relevant character rather than strictly above it. For instance, is to be interpreted as having the overbar designation directly above the "X"', i.e., the keypoint Brief Description of the Figures

A preferred embodiment of the invention will now be described, by way of example only, with reference to the accompanying drawings in which:

FIG. 1 shows an exemplary arrangement of a preferred embodiment of the present invention;

FIG. 2 explains the 2D to 3D feature matching process implemented on the processor circuit;

FIG. 3 depicts two different means of implementing the RANSAC operation of the inventive methods; and

FIG. 4 depicts circle restricting 2D feature detection to the vicinity of the 3D point to resolve scale ambiguity. Using the 2D detector on each orientation plane represented by a matrix in , through the 3D keypoint at the initial scale of the volume, estimates the corresponding 2D scale for the 3D keypoint. Detection is allowed to happen in a radius to counter misregistration of 3D keypoint detection. In FIG. 4, the CT volume is designated [40]; the feature circle (the circle restricting 2D feature detection in the vicinity of the 3D point to solve scale ambiguity) is [41]; the 3D keypoint is [42]; the extract patch is [43] and the 2D feature detection of the extracted plane is designated [44]. Detailed Description of the Preferred Embodiments

Image registration of 2D images and 3D volumes has many industrial and medical applications. Industrial applications include grain structure analysis, data fusion for fault detection. State of the art 2D-3D registration techniques are computationally expensive. For example, registration of a Mega-pixel 2D image to a Giga-voxel 3D volume computation time is in many hundreds of CPU hours utilizing state of the art CPU technology.

The present invention introduces repeatable keypoint detection for 2D images and 3D volumes, a novel way of descriptor formation for matching 2D keypoints and 3D keypoints and model estimation for registration up to an affinity under low feature matching accuracy. The invention relates to an affine registration estimation based on an algorithm, which requires three true positive matches of feature points and extend this to estimate the model based on only a single true positive match, which we call the one-point algorithm. In addition, handling image scale is also addressed by resolving the ambiguity of 2D image scale and 3D image scale. The Applicant demonstrates that 2D scale and 3D scale do not represent similar image and volume neighborhoods. The Applicant compares the inventive technique with state of the art global registration techniques, such as correlation based registration and indicate the superior performance of the inventive method which is several hundred times faster.

The arrangement in FIG. 1 shows an exemplary arrangement of a preferred embodiment. The apparatus in arrangement FIG. 1 includes a 3D scanner [1] shown generally, which can be any 3D source like a micro CT scanner scanning an object [2] and a 2D scanner [3] shown generally, which can be any 2D source like a electron microscope scanning any section of the object [2]. The 2D section [4] captured from the 2D scanner [3] is sent to the computer [5] along with the 3D scan [6]. Effectively the computer [5] is programmed to solve the problem of registering 2D-3D images by detecting repeatable point features in 2D-3D images, describing them with descriptors, successfully matching them, finding correspondences and estimating registration by rejecting outliers using RANSAC.

The block diagram in FIG. 2 explains the 2D to 3D feature matching process implemented on the processor circuit. First the 3D scanner generates a 3D volume [7] of the object of interest. The 3D point feature detector [8], comprises a 3D DoG point feature detector formulated by extrema detection, a stability test and interpolation steps. For the 3D case, scale is not used when detecting extrema. Using scale also for extrema detection reduces the number of keypoints considerably, hence leading to lower repeatability. Then, these detected extrema are chosen as keypoints after the stability test and interpolation to sub-pixel accuracy. Interpolation is performed by fitting the keypoint extrema response to a Taylor series. For each generated 3D keypoint, region extractor [9] resamples planes through that point, with orientation chosen among all possible orientations. Subsequently, 2D features are computed on this resampled plane to produce matchable descriptors with the 2D image. Thus, for the 3D case, we use bilinear interpolation to compute sampled planes through each 3D keypoint before computing descriptors. One 3D keypoint has many descriptors (typically the number of differently oriented planes). For convenience, we take a nearly equally spaced set of radially outward vectors in a sphere as possible orientations for the sample planes. The 2D scanner [10] scans for interest points on all selected planes and descriptors are generated for each interest point. The processor circuit is programmed to associate [13] these descriptors with their corresponding keypoints. Next the 2D scanner generates a 2D image [14] section of the object of interest. The 2D point feature detector [15] detects interest points of the 2D image and 2D descriptors [16] are extracted from the image. These descriptors of the 2D image are then matched [17] with descriptors generated for the 3D volume. Finally the system employs an image model [18] with RANSAC for outlier rejection.

A feature point, such as one produced by the DoG feature point extractor assigns an intrinsic scale to any feature point, determined by response of the detector to filtered versions of the image computed by convolution of different kernels.

Because convolution (filtering) cannot be interchanged with taking slices of an image volume, the scale assigned to a 3D feature will not generally be the same as the scale assigned to the corresponding 2D feature in a local 2D image slice. That is let E : R ² → R ³ be an operator that selects a 2D slice from the 3D image volume, and let / : R ³ → R represent the intensity (voxel value) at a point in the 3 volume. Then 1 ° E : R ² → R is the intensity function on the 2D image slice. If g is a Gaussian convolution kernel and star * represents the convolution (filtering) operation, then generally, (g * I ) ⁰ E≠ g * (1 ⁰ E)). The first is the result of slicing the filtered 3D image, whereas the second is the result of filtering the sliced 2D image. This indicates that a descriptor computed on the convolved volumes artificial slice is not the same as a descriptor computed on a convolved artificial slice of a volume. Thus, there is an ambiguity in the scale of 2D-3D keypoints, which needs to be resolved in order to improve matching accuracy.

For each 3D keypoint, obtaining patches corresponding to transformation matrices on its 3D scale is not meaningful because of the above mentioned scale ambiguity. Thus, we take the planes through a keypoint according to Q( ) from the initial volume (volume at starting scale) and run the 2D detector on each slice again constrained to the vicinity of the 3D keypoint. This region of 2D detection is represented by a feature circle in FIG. 4. With 2D keypoints detected in this case are chosen as scales for the 3D point and descriptors are computed on them, which effectively solves the scale ambiguity as shown in FIG. 4.

Let be the descriptor of a 3D keypoint corresponding to the k ^th plane, be the descriptor of a 2D keypoint and ) be a descriptor of the 3D keypoint X, without explicit specification of the plane it belongs to.

We use KNN (K Nearest neighbor) to match a 2D feature with the K best matches in the 3D volume, thereby providing multiple hypotheses for the best matching 3D feature. This is because matching closely oriented planes has an accuracy far below general descriptor matching. We use only a finite number of sample planes through a 3D keypoint for the descriptor computation (FIG. 4).

Therefore, any 3D keypoint will have only a closely oriented sample plane corresponding to the 2D key- point patch. When the plane orientation changes, the patch structure changes; thus, the descriptor computed on it changes. This reduces the descriptor matching accuracy. Let H be the hypothesis set of 2D-3D

correspondences obtained by KNN feature matching. Let be the set of KNN feature descriptors to where (1) where v is a set of features in the 2D slice.

We expect that H has true positive correspondences. In the next step, we use RAN SAC to estimate the model T from H.

The RANSAC operation is implemented in two different ways in FIG. 3. In the first way which we call the 1 point [19] implementation we use scale

information, in many practical registration problems, it can be assumed that the relative scale of the 2D and 3D images is known and the scales in each direct ion are the scale is approximately constant in every direction. In fact for Micro-CT and SEM ac qu isition devices, the scale can be kno wn as a property of the imaging devices. Let be true correspondences. Under these

conditions the following holds

where represent the true physical distance between the

features, taking into account the kno wn scale of the imaging devices. Further S is an adjustment for corner detection misregistration. If the scales are known only approximately, then this condition can be relaxed accordingly by choosing an appropriate value for We define a set of pairs to be compatible with each other if they satisfy the relation (Eq. 2). The above relation can be used to reduce the number of true positive correspondences needed for correctly estimating the model. Let us say we pick a true positive correspondence. Now; the other two correspondences can be found by the above constraint, in fact, we need only one true positive point to correctly estimate the model

Also the block diagram shows an alternate processor circuit implementation which selects 3 points [22] to generate the model and do RANSAC RANSAC [23].

Although the invention has been described with reference to specific examples it. will be appreciated by those skilled in the art that the invention may be embodied in many other forms.