Материал: [2.1] 3D Imaging, Analysis and Applications-Springer-Verlag London (2012)

are only interested in the final registration error between the two surfaces. A fuller and more formal outline of ICP is presented in the following subsection.

8.6.1 ICP Outline

Let pj = [xj yj zj ]T where j = 1 . . . M be a zero-mean set of 3D points of a probe face scan and let gi = [xi yi zi ]T where i = 1 . . . N be a zero-mean set of 3D points of a gallery face scan. Since both point clouds are zero mean, they have an implicit coarse translational alignment. An initial coarse orientation alignment may also be required to avoid convergence to a local minimum but, for now, we will assume that it is not required and we will discuss this issue later.

where c and d are vectors of size M each, such that c and d contain, respectively, the index number and distance of the j th point of P to its nearest point in G. This is called the closest points step where the pairs of closest points within the two point clouds are assigned as tentative correspondences. (We use the word tentative because they are not accurate correspondences until ICP has converged to the correct global minimum.) This is the most critical and computationally the most expensive step of the algorithm. It is critical because highly inaccurate tentative correspondences could, in the worst case, cause ICP convergence to a local minimum. Even if this is not the case, they will affect the accuracy of the final registration and hence the matching metric between the two point clouds. Typically, the following filters are applied to minimize these effects:

1.Tentative correspondences whose distance is greater than a threshold are removed. The threshold is usually chosen as a multiple of the point cloud resolution which is initially set relatively high, depending on the quality of the initial registration. It is then gradually reduced through the iterations until it is equal to the resolution.

2.Tentative correspondences whose surface normals have a mutual angle above a threshold are removed. The threshold is chosen based on the accuracy of the normals and the quality of the initial registration. Also, it is possible to reduce this threshold through the iterations.

3.Tentative correspondences at the boundary points are avoided. This step is useful when the two point clouds only partially overlap, as occurs with partial views of the probe face.

4.Sometimes additional information such as texture is also used to remove poor quality tentative correspondences.

To speed up the search for nearest points within the gallery scan, the points in each gallery scan are arranged in a k-d tree (see Chap. 4) and these structures are precomputed offline. A further speed up can be achieved by storing the index of the nearest neighbor from the centers of a set of voxels in a voxelized space around the gallery scan [91]. Again this can be precomputed offline. (Note that the ICP technique based on Levenberg-Marquardt minimization [34], described in Chap. 6,

also uses a pre-computed distance transform.)

Let pk = [xk yk zk ]T and gk = [xk yk zk ]T (where k = 1 . . . m) be the remaining m corresponding pairs of points of the probe and gallery face respectively. The next step is to find the rotation matrix R and translation vector t that minimizes the mean square error (MSE) between these tentative correspondences. The error to be minimized is given by:

The unknowns (R and t) in Eq. (8.3) can be calculated using a number of approaches including quaternion methods and Singular Value Decomposition (SVD). We will give details of the widely-used SVD approach [7]. The means of pk and gk are given by

where Pm, Gm are the zero-centered data matrices in Eq. (8.1) trimmed to m × 3 matrices of m tentative correspondences. Performing the SVD of C gives us:

where U and V are two orthogonal matrices and S is a diagonal matrix of singular values. The rotation matrix R can be calculated from the orthogonal matrices as [7]:

Note that if this is indeed a rotation matrix, then det(R) = +1. However, in principle, it is possible to obtain det(R) = −1, which corresponds to a reflection. This degeneracy is not what we want but, according to Arun et al. [7] and in our own experience, it usually does not occur. Once the rotation matrix has been computed, the translation vector t can be calculated as:

where J1,n is a 1 × n matrix of ones.

Subsequently, tentative correspondences are established again between the transformed probe face and the gallery face (Eq. (8.2)). This process is iterated until e approaches a minimum value, detected by its change over one iteration falling below some threshold. If the initial coarse alignment is within the convergence zone of the global minimum MSE, the final value of e is a good measure of the similarity between two face scans, where smaller values of e mean that the faces are more similar. In identification scenarios, the probe face is matched with every gallery face and the identity of the one with the minimum value of e is declared as the probe’s identity. If two gallery identities have very similar low e values, sometimes the number of correspondences, m, in the final iteration can also be used to make a better judgement. Alternatively, a probe can be verified against a claimed gallery identity if the computed value of e falls below some appropriate threshold.

8.6.2 A Critical Discussion of ICP

The main advantage of the ICP algorithm is that it iteratively corrects registration errors as it matches two faces, provided that the initial alignment of the surfaces is within the zone of convergence of the global minimum. If the initial coarse registration is not good enough ICP can converge to a local minimum and hence the algorithm fails. Iterative realignment comes at a heavy computational cost, particularly in the establishment of closest points. For this step, a basic search has complexity O(MN ), where M and N are the number of points in the probe and gallery scans respectively. This is reduced to O(M log N ) when using k-d tree structures for the closest points search in the gallery scans. It is important to remember that the average time per gallery scan match is also scaled by the average number of iterations per match which is often different for different ICP variants.

Another disadvantage of ICP is that it does not extract features from the face, thus ruling out the possibilities of training classifiers on multiple instances of a face, and ruling out indexing of features from gallery faces for faster matching or feature-level fusion. Thus, the probe must be matched to the complete gallery, thereby making the recognition time linear to the gallery size. This means that, in relation to scan resolution and gallery size, NG, a single ICP-based probe to gallery match has overall complexity O(NGM log N ).

As a consequence of this, many variants of ICP try to reduce the face scan match time. Coarse to fine resolution schemes can be used and we can precompute as many aspects of the algorithm as possible on the whole gallery in an offline batch process. Examples include extracting fiducial points for coarse registration, cropping to spherical volumes relative to the nose tip, building k-d trees and placing the galley scans in voxel structures for fast look up of closest points.

The ICP algorithm can accurately match rigid surfaces. However, faces are not rigid and the facial surface can significantly deform due to expressions. Consequently, the performance of standard ICP degrades under facial expressions. For example, one study cropped the 3D face region manually and then applied standard ICP for neutral and non-neutral subsets of the FRGC dataset for a rank-1 recognition test. The neutral dataset gave an average result of 91 % while the non-neutral subset was only 61.5 % [19].

However, a second advantage of ICP is that it can operate in partial surface matching schemes. Thus the problem of facial expressions can be significantly mitigated by applying ICP to the relatively rigid regions of the face [19, 64], which can be identified in the gallery scans in an offline batch process. The ability to do partial matching also allows ICP to handle pose variations by matching 2.5D scans to complete face models [59]. In the case of large pose variations, coarse prealignment using fiducial points (landmarks) may be necessary.

8.6.3 A Typical ICP-Based 3D Face Recognition Implementation

We now outline typical steps involved in a standard ICP-based 3D face recognition application. This is intended as a guide on how to implement and start using this approach, but please note that there are many variants of this algorithm available in the literature. A MATLAB implementation of ICP can be downloaded and adapted as necessary from [63].

We assume that the probe and gallery faces are near-frontal in pose. Some minor pose variations are allowable, such as is found in the FRGC v2 dataset and as might be seen in a typical cooperative verification application. Padia and Pears [69] show that, when registering a 3D face scan to an average face model, ICP converges to the correct global minimum for an initial misalignment between the scans of at least 30 degrees in any of three orthogonal rotational axes. We preprocess each gallery scan, according to the steps below.

1.Determine the closest vertex to the camera. In most reasonable quality scans, this will be close to the nose-tip. (Occasionally, the chin, lips or forehead can be closest to the camera and, in a first implementation, a quick visual check may be required so that the nose tip can be selected manually for these failure cases.)

2.Crop to a spherical region of radius 100 mm around this point. For smaller faces this may include some neck and hair area.

3.Filter spikes and interpolate over any holes.

4.Compute the mean of the point cloud and perform a zero-mean operation (i.e. subtract the mean from each vertex).

5.Use an off-the-shelf algorithm to organize each gallery scan into a k-d tree. Many are publicly available on the web.

For each probe scan to be matched to the gallery, we follow the steps below.

1.Perform the processing steps 1–4 described for the gallery scans above. Given that both probe and gallery face scans are now zero-mean, this constitutes an initial coarse translational alignment.

2.Use a standard off-the-shelf algorithm to perform a closest-point search in the k-d tree of the gallery scan, for each point in the probe scan.

3.Delete tentative correspondences according to the filters given in the earlier 4- point list. (Use the distance and surface normal filters, at least.)

4.From the tentative correspondences, form the cross-covariance matrix using Eq. (8.7). (Note that the means used for this matrix are associated with the list of filtered tentative correspondences, not the full scans.)

5.Perform SVD on the cross-covariance matrix and hence extract the rotation matrix, R, according to Eq. (8.9).

6.Compute the translation, t using Eq. (8.10).

7.Update the alignment of the probe scan with the gallery scan using Eq. (8.11).

8.Compute e and, unless on first iteration, determine the change in e from the previous iteration. If this is below a threshold, or if the maximum number of iterations has been reached, finish. Otherwise go to step 2.

The smallest final value of e is used to determine the best match in the gallery for a rank-1 identification, although if e is not sufficiently low, it could be determined that the probe subject is not present in the gallery. Alternatively, the e value could be determined from a single gallery face scan match and thresholded in a verification test against a claimed gallery identity.

Once this basic implementation described above is operational, there are several immediate improvements that can be made. For those readers that want to improve the implementation, we suggest the following.

•The final number of correspondences may vary and this number may be included, along with e, in a cost function in order to make the verification or identification decision. (i.e. A slightly higher e value could be preferable if it is accompanied by a significantly higher number of correspondences.)

•Particularly for large datasets where a fast per-scan match is required, it is preferable to construct a voxel space around the gallery scans where, for the center of each voxel, the index of the nearest gallery surface point is stored. This means that for some probe point, we determine the voxel that it lies in and we just look up the corresponding gallery surface point [91].

When dealing with large pose variations of the probe, such as may be encounted in a non-cooperating subject identification scenario, more sophisticated techniques than the above are required. The cropping of the probe based on the nose-tip being the nearest point to the camera will often fail and, in profile views, the nose tip will