PointSetRegistrationCoherentPointDrift_CoherentPointDrift资源-CSDN文库

4星 · 超过85%的资源需积分: 23 162 浏览量 2011-04-18 16:10:46 上传评论收藏 2.18MB PDF 举报

### Point Set Registration: Coherent Point Drift (CPD) #### 引言点集配准是计算机视觉领域中的一个核心问题，在许多应用中都扮演着关键角色，如立体匹配、基于内容的图像检索、图像配准及形状识别等。点集配准的主要目标在于为两组点之间建立对应关系，并恢复将一组点映射到另一组点的变换。这一过程面临着多种挑战，包括未知的非刚性空间变换、点集的大维数性、噪声以及离群点的存在等。 #### Coherent Point Drift (CPD) 算法介绍针对上述问题，Andriy Myronenko 和 Xubo Song 提出了 Coherent Point Drift（CPD）算法，该方法适用于刚性和非刚性的点集配准问题。CPD 算法的核心思想是将两个点集之间的对齐视为概率密度估计问题。具体来说，该算法将表示第一个点集的高斯混合模型（GMM）质心与第二个点集的数据进行拟合，通过最大化似然函数来完成这个过程。为了保持点集间的拓扑结构，CPD 算法强制 GMM 质心以一种一致的方式移动。在刚性情况下，一致性约束通过刚性参数重新参数化 GMM 质心的位置来实现，并推导出任意维度下的期望最大化（EM）算法的最大化步骤的闭式解。而在非刚性情况下，则通过对位移场进行正则化并利用变分微积分来求解最优变换。 #### 刚性配准在刚性配准问题中，假设两组点之间的变换是刚性的，即只包含平移和旋转。CPD 通过重新参数化 GMM 质心的位置来确保这些质心的移动符合刚性变换的要求。具体而言，每个质心的位置可以通过平移向量和旋转矩阵来表示。这种方法的关键在于能够推导出 EM 算法最大化步骤的闭式解，这意味着无需进行复杂的数值优化过程即可找到最佳变换参数。此外，这种方法在任意维度下均有效，从而提高了算法的通用性和灵活性。 #### 非刚性配准在处理非刚性配准时，两组点之间的对应关系可能涉及更复杂的变形模式，例如扭曲或拉伸。CPD 算法通过引入一致性约束来解决这类问题，这种约束确保了点集之间变换的一致性和连续性。一致性约束通过正则化位移场来实现，这种方法可以避免点集间的拓扑结构被破坏。通过使用变分微积分，可以有效地求解最优变换，即使是在复杂变形的情况下也能得到较好的配准结果。 #### 快速算法为了进一步提高 CPD 算法的效率，研究者还提出了一种快速版本的 CPD 方法。该方法通过减少计算复杂度至线性级别，使得算法能够在大规模数据集上高效运行。这对于实时应用或者处理大量数据的应用场景尤其重要。 #### 实验结果 CPD 算法在不同条件下的实验结果表明，其在噪声、离群点和缺失点存在的情况下仍能准确地进行配准，并且在性能上超越了现有的先进方法。这证明了 CPD 算法在处理实际问题时的强大能力。 #### 结论 Coherent Point Drift 算法提供了一种新颖而有效的点集配准解决方案，无论是对于刚性还是非刚性配准问题都有着出色的表现。通过结合概率建模和一致性约束的思想，CPD 算法能够在复杂的环境中稳健地工作，为计算机视觉领域的多个应用场景提供了强有力的支持。

资源推荐

资源详情

资源评论

Point Set Registration: Coherent Point Drift

Andriy Myronenko and Xubo Song

Abstract—Point set registration is a key component in many computer vision tasks. The goal of point set registration is to assign

correspondences between two sets of points and to recover the transformation that maps one point set to the other. Multiple factors,

including an unknown nonrigid spatial transformation, large dimensionality of point set, noise, and outliers, make the point set

registration a challenging problem. We introduce a probabilistic method, called the Coherent Point Drift (CPD) algorithm, for both rigid

and nonrigid point set registration. We consider the alignment of two point sets as a probability density estimation problem. We fit the

Gaussian mixture model (GMM) centroids (representing the first point set) to the data (the second point set) by maximizing the

likelihood. We force the GMM centroids to move coherently as a group to preserve the topological structure of the point sets. In the

rigid case, we impose the coherence constraint by reparameterization of GMM centroid locations with rigid parameters and derive a

closed form solution of the maximization step of the EM algorithm in arbitrary dimensions. In the nonrigid case, we impose the

coherence constraint by regularizing the displacement field and using the variational calculus to derive the optimal transformation. We

also introduce a fast algorithm that reduces the method computation complexity to linear. We test the CPD algorithm for both rigid and

nonrigid transformations in the presence of noise, outliers, and missing points, where CPD shows accurate results and outperforms

current state-of-the-art methods.

Index Terms—Registration, correspondence, matching, alignment, rigid, nonrigid, point sets, Coherent Point Drift (CPD), Gaussian

mixture model (GMM), coherence, regularization, EM algorithm.

1INTRODUCTION

EGISTRATION of point sets is a key component in many

computer vision tasks, including stereo matching,

content-based image retrieval, image registration, and

shape recognition. The goal of point set registration is to

assign correspondences between two sets of points and/or

to recover the transformation that maps one point set to the

other. For example, in stereo matching, in order to recover

depth and infer structure from a pair of stereo images, it is

necessary to first define a set of points in each image and

find the correspondence between them. An example of a

point set registration problem is shown in Fig. 1. The

“points” in a point set are often features extracted from an

image, such as the locations of corners, boundary points, or

salient regions. The points can represent both geometric and

intensity characteristics of an image.

Practical point set registration algorithms should have

several desirable properties: 1) the ability to accurately

model the transformation required to align the point sets

with tractable computational complexity, 2) the ability to

handle possibly high dimensionality of the point sets, and

3) robustness to degradations such as noise, outliers, and

missing points that occur due to imperfect image acquisition

and feature extraction.

The transformation usually falls into two categories:

rigid or nonrigid. A rigid transformation only allows for

translation, rotation, and scaling. The simplest nonrigid

transformation is affine, which also allows anisotropic

scaling and skews. Nonrigid transformation occurs in many

real-world problems, including deformable motion track-

ing, shape recognition, and medical image registration. The

true underlying nonrigid transformation model is often

unknown and challenging to model. Simplistic approxima-

tions of the true nonrigid transformation, including piece-

wise affine and polynomial models, are often inadequate for

correct alignment and can produce erroneous correspon-

dences. Due to the usually large number of transformation

parameters, the nonrigid point set registration methods tend

to be sensitive to noise and outliers and are likely to converge

into local minima. They also tend to have a high computa-

tional complexity. A practical nonrigid point set registration

method should be able to accurately model the nonrigid

transformation with tractable computational complexity.

Multidimensional point sets are common in many real-

world problems. Most current rigid and nonrigid point set

registration algorithms are well suited for 2D and 3D cases,

but their generalizations to higher dimensions are not

always trivial. Furthermore, degradations such as noise,

outliers, and missing points significantly complicate the

problem. Outliers are the points that are incorrectly

extracted from the image; outliers have no correspondences

in the other point set. Missing points are the features that

are not found in the image due to occlusion or inaccurate

feature extraction. A point set registration method should

be robust to these degradations.

We present a robust probabilistic multidimensional point

set registration algorithm for both rigid and nonrigid trans-

forms. We consider the alignment of two point sets as a

probability density estimation problem, where one point set

represents the Gaussian Mixture Model (GMM) centroids

and the other one represents the data points. We fit the GMM

2262 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 32, NO. 12, DECEMBER 2010

. The authors are with the Department of Science and Engineering, School of

Medicine, Oregon Health and Science University, 20000 NW Walker

Road, Beaverton, OR 97006.

E-mail: myron@csee.ogi.edu, xubosong@bme.ogi.edu.

Manuscript received 16 Apr. 2009; revised 5 Nov. 2009; accepted 10 Nov.

2009; published online 25 Feb. 2010.

Recommended for acceptance by F. Kahl.

For information on obtaining reprints of this article, please send e-mail to:

tpami@computer.org, and reference IEEECS Log Number

TPAMI-2009-04-0240.

Digital Object Identifier no. 10.1109/TPAMI.2010.46.

0162-8828/10/$26.00 ß 2010 IEEE Published by the IEEE Computer Society

centroids to the data by maximizing the likelihood. At the

optimum, the point sets become aligned and the correspon-

dence is obtained using the posterior probabilities of the

GMM components. Core to our method is forcing GMM

centroids to move coherently as a group, which preserves the

topological structure of the point sets. We impose the

coherence constraint by explicit reparameterization of

GMM centroid locations (for rigid and affine transforma-

tions) or by regularization of the displacement field (for

smooth nonrigid transformation). We also show how the

computational complexity of the method can be reduced to

linear, which makes it applicable for large data sets. The rest

of the paper is organized as follows: In Section 2, we overview

the current rigid and nonrigid point set registration methods

and state our contributions. In Section 3, we formulate a

probabilistic point set registration framework. In Sections 4

and 5, we describe our algorithms for rigid, affine, and

nonrigid registration cases, and relate them to existing works.

In Section 6, we discuss the computational complexity of the

method and introduce its fast implementation. In Section 7,

we evaluate the performance of our algorithm. Section 8

concludes with some discussions.

2PREVIOUS WORK

Many algorithms exist for rigid and for nonrigid point set

registration. They aim to recover the correspondence or the

transformation required to align the point sets or both. Many

algorithms involve a dual-step update, iteratively alternat-

ing between the correspondence and the transformation

estimation. Here, we briefly overview the rigid and nonrigid

point set registration methods and state our contributions.

2.1 Rigid Point Set Registration Methods

The Iterative Closest Point (ICP) algorithm, introduced by

Besl and McKay [1] and Zhang [2], is the most popular

method for rigid point set registration due to its simplicity

and low computational complexity. ICP iteratively assigns

correspondences based on the closest distance criterion and

finds the least-squares rigid transformation relating the two

point sets. The algorithm then redetermines the correspon-

dences and continues until it reaches the local minimum.

Many variants of ICP have been proposed that affect all

phases of the algorithm from the selection and matching of

points to the minimization strategy [3], [4]. ICP requires that

the initial position of the two point sets be adequately close.

To overcome the ICP limitations, many probabilistic

methods were developed [5], [6]. These methods use

soft assignment of correspondences that establishes

correspondences between all combinations of points

according to some probability which generalizes the

binary assignment of correspondences in ICP. Among

these methods are the Robust Point Matching (RPM)

algorithm introduced by Gold et al. [7], and its later

variants [5], [8]. In [9], it was shown that, in RPM,

alternating soft assignment of correspondences and trans-

formation is equivalent to the Expectation Maximization

(EM) algorithm for GMM, where one point set is treated as

GMM centroids with equal isotropic covariances and the

other point set is treated as data points. In fact, several rigid

point set methods, including Joshi and Lee [10], Wells [11],

Cross and Hancock [12], Luo and Hancock [6], [13], McNeill

and Vijayakumar [14], explicitly formulate point set regis-

tration as a maximum likelihood (ML) estimation problem

to fit the GMM centroids to the data points. These methods

reparameterize GMM centroids by a set of rigid transfor-

mation parameters (translation and rotation). The EM

algorithm used for optimization of the likelihood function

consists of two steps: E-step to compute the probabilities

and M-step to update the transformation. Common to such

probabilistic methods is the inclusion of an extra distribu-

tion term to account for outliers (e.g., large Gaussian [5] or

uniform distribution [11]) and deterministic annealing on

the Gaussian width to avoid poor local minima. These

probabilistic methods perform better than conventional

ICP, especially in the presence of noise and outliers.

Another class of rigid point set registration methods is

the spectral m ethods. Scott and Longuet-Higgins [15]

introduced a noniterative algorithm to associate points of

two arbitrary patterns, e xploiting some properties of

Gaussian proximity matrix (Gram matrix) of point sets.

The algorithm works well with translation, shearing, and

scaling deformations, but performs poorly with nonrigid

transformations. Li and Hartley showed that correspon-

dence and transformation are two factors of Gram matrices

that can be found iteratively using Newton-Schulz factor-

ization [16]. This method performs well for moderate linear

transformations. In spite of its elegance, the large computa-

tional effort required for spectral methods prohibits its wide

applicability. There are a few other nonspectral methods

worth mentioning. Ho et al. [17] proposed an elegant

noniterative algorithm for 2D affine registration by search-

ing for the roots of the associated polynomials. Unfortu-

nately, this method does not generalize to higher

dimensions. Belongie et al. [18] introduced the “shape

context” descriptor, which incorporates the neighborhood

structure of the point set and thus helps to recover the

correspondence between the point sets.

Our approach to the rigid point set registration is

probabilistic and most closely related to the works of

Rangarajan et al. [5], Wells [11], and Luo and Hancock [13].

Despite extensive work in rigid probabilistic registration,

none of the methods, to the best of our knowledge, provides

a closed form solution to the maximization step (M-step) of

the EM algorithm for a general multidimensional case. The

fact that the rotation matrix should be constrained to be

orthogonal and to have a positive determinant further

complicates its estimation. Rangarajan et al. [5] showed the

solution for the 2D case only, where rotation is parameter-

ized by a single angle. In higher dimensions, the closed

MYRONENKO AND SONG: POINT SET REGISTRATION: COHERENT POINT DRIFT 2263

Fig. 1. The point set registration problem: Given two sets of points,

assign the correspondences and the transformation that maps one point

set to the other.

form solution with Euler angles parameterization is not

feasible. Luo and Hancock [6], [13] find the rotation matrix

through singular value decomposition (SVD). They ignore

some terms of the objective function, which leads to only an

approximate solution. We shall derive the exact closed form

solution (M-step) for the rigid point set registration and

discuss its difference from the related methods in Section 4.

2.2 Nonrigid Point Set Registration Methods

Earlier works on nonrigid point set registration include

Hinton et al. [19], [20], who used the probabilistic GMM

formulation. The GMM centroids are uniformly positioned

along the contour (modeled using splines), which allows for

nonrigid transformations. In practice, the method is applic-

able only to contour-like point sets. One of the most popular

nonrigid point set registration method is by Chui and

Rangarajan [8]. They proposed using Thin Plate Spline

(TPS) [21], [22] parameterization of the transformation,

following RPM, which results in the TPS-RPM method.

Similarly to the rigid case, they use deterministic annealing

and alternate updates for soft assignment and TPS para-

meters estimation. They also showed that TPS-RPM is

equivalent (with several modifications) to EM for GMM [9].

Tsin and Kan ade [ 23] proposed a correlation-ba sed

approach to point set registration, which was later

improved by Jian and Vemuri [24]. The method considers

the registration as an alignment between two distributions,

where each of the point sets represents the GMM centroids.

One of the point sets is parameterized by rigid/affine

parameters (in the rigid/affine case) or TPS (in the nonrigid

case). The transformation parameters are estimated to

minimize the L

norm between the distributions. These

methods all use explicit TPS parameterization, which is

equivalent to a regularization of second order derivatives of

the transformation [21], [22]. The TPS parameterization

does not exist when the dimension of points is higher than

three, which limits the applicability of such methods.

Huang et al. [25] proposed implicitly embedding the

shape (or point sets in our case) into distance transform

space and aligning them similarly to nonrigid image

registration algorithms. The authors use sum-of-squared-

differences similarity measure between the embedded

spaces and incremental free form deformation (FFD) to

parameterize the transformation. The method performs

well on relatively simple data sets.

Finally, in our previous work, we presented the Coherent

Point Drift (CPD) algorithm [26] for nonrigid point set

registration. The algorithm regularizes the displacement

(velocity) field between the point sets following the motion

coherence theory (MCT) [27], [28]. Using variational

calculus, we obtained that the optimal displacement field

has an elegant kernel form in multiple dimensions. In this

paper, we shall elaborate and analyze the CPD algorithm.

We also extend the general nonrigid registration framework

and show that CPD and TPS-RPM are its special cases.

Among other contributions, we estimate the width of GMM

components without the time-consuming deterministic

annealing and show a fast CPD implementation to reduce

the computational complexity to linear. We shall discuss

and compare o ur method to the works of Chui and

Rangarajan [8] and Jian and Vemuri [24] in Section 5.

3GENERAL METHODOLOGY

We consider the alignment of two point sets as a probability

density estimation problem, where one point set represents

the GMM centroids and the other one represents the data

points. At the optimum, two point sets become aligned and

the correspondence is obtained using the maximum of the

GMM posterior probability for a given data point. Core to

our method is to force GMM centroids to move coherently

as a group to preserve the topological structure of the point

sets. Throughout the paper, we use the following notations:

. D—dimension of the point sets,

. N;M—number of points in the point sets,

. X

ND

¼ðx

; ...; x

—the first point set (the data

points),

. Y

MD

¼ðy

; ...; y

—the second point set (the

GMM centroids),

. TðY;Þ—Transformation T applied to Y, where  is

a set of the transformation parameters,

. I—identity matrix,

. 1—column vector of all ones,

. dðaÞ—diagonal matrix formed from the vector a.

We consider the points in Y as the GMM centroids and the

points in X as the data points generated by the GMM. The

GMM probability density function is

pðxÞ¼

Mþ1

m¼1

PðmÞpðxjmÞ; ð1Þ

where pðxjmÞ¼

ð2

D=2

exp



xy

kk2

2

. We also added an

additional uniform distribution pðxjM þ 1Þ¼

to the

mixture model to account for noise and outliers. We use

equal isotropic covariances 

and equal membership

probabilities P ðmÞ¼

for all GMM components

(m ¼ 1; ...;M). Denoting the weight of the uniform

distribution as w, 0  w  1, the mixture model takes

the form

pðxÞ¼w

þð1  wÞ

m¼1

pðxjmÞ: ð2Þ

We reparameterize the GMM centroid locations by a set of

parameters  and estimate them by maximizing the

likelihood or, equivalently, by minimizing the negative

log-likelihood function

Eð; 

Þ¼

n¼1

log

Mþ1

m¼1

PðmÞpðx

jmÞ; ð3Þ

where we make the i.i.d. data assumption. We define the

correspondence probability between two points y

and x

as the posterior probability of the GMM centroid given the

data point: P ðmjx

Þ¼PðmÞpðx

jmÞ=pðx

Þ.

We use the EM algorithm [29], [30] to find  and 

. The

idea of EM is first to guess the values of parameters (“old”

parameter values) and then use the Bayes’ theorem to

compute a posteriori probability distributions P

old

ðmjx

Þ of

mixture components, which is the expectation or E-step of

the algorithm. The “new” parameter values are then found

2264 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 32, NO. 12, DECEMBER 2010

剩余13页未读，继续阅读

评论收藏

内容反馈

y1234ou

2016-10-26

里面只是论文

xiechuang38

粉丝: 2
资源: 5

Point Set Registration Coherent Point Drift

最新资源

Point Set Registration Coherent Point Drift

point set registration

相干点漂移

一 致 性 点 漂 移 算 法 (Coherent Point Drift, CPD)

CPD点集配准.zip

CPD(Coherent Point Drift)相干点漂移算法.zip

Non-Rigid Point Set Registration

论文研究-Highly coherent supercontinuum generation in the normal dispersion liquid-core photonic crystal fiber.pdf

matlab集成c代码-coherent_point_drift_cuda:使用CUDA实现相干点漂移算法（Myronenko和Song，20

Point-Set-Registration:点集注册-相干点漂移

Matlabconcavepointmatchingsourcecode-Point-Set-Matching-Registration-Ma

层次分析matlab代码-Point-Set-Registration-of-CIM:CIM点集注册

CPD.rar_CPD_Coherent Point Drift_Gabor filter_coherent_cpd.rar

matlab噪声点的判断代码-drift:自动校正眼动数据垂直漂移的算法

vehicle-drift-master 漂移仿真_Matlab,Carsim_C++_vehicle_master车_车辆漂

用TEXONO和COHERENT数据约束光子入口暗物质

CPD-matlab工具箱

dma_mask与coherent_dma_mask

CPD2 matlab_package.zip

dma.c驱动分析

Coherent LMS Algorithm

A State-Space Technique for Ultrawide-Bandwidth Coherent Processing

使用概率模型(相干点漂移，GMMReg, SVR, GMMTree, FilterReg, Bayesian CPD)进行点云配准的Python包- neka-nat/probreg

coherent system

digital-optical-coherent-detection.rar_coherent_coherent detecti

使用COHERENT能量和定时数据改进了对非标准中微子相互作用的整体拟合

在COHERENT数据后测试具​​有任意介体质量的大型非标准中微子相互作用

Coherent.rar_coherent_matlab

Visualizing Lagrangian Coherent Structures

Coherent_and_Non-coherent_MIMO_Radar_Techniques_for_Target_Localization.pdf

Ultra-wideband Coherent Processing

最新资源

一致性点漂移算法 (Coherent Point Drift, CPD)

在COHERENT数据后测试具有任意介体质量的大型非标准中微子相互作用