Point set registration

In computer vision and pattern recognition, point set registration, also known as point matching, is the process of finding a spatial transformation that aligns two point sets. The purpose of finding such a transformation includes merging multiple data sets into a globally consistent model, and mapping a new measurement to a known data set to identify features or to estimate its pose. A point set may be raw data from 3D scanning or an array of rangefinders. For use in image processing and feature-based image registration, a point set may be a set of features obtained by feature extraction from an image, for example corner detection. Point set registration is used in optical character recognition, augmented realityand aligning data from magnetic resonance imaging with computer aided tomography scans. T ( M ) {displaystyle T({mathcal {M}})}     (1) T ( M , θ ) {displaystyle T({mathcal {M}}, heta )}     (2) dist ⁡ ( T ( M ) , S ) = ∑ m ∈ T ( M ) ∑ s ∈ S ( m − s ) 2 {displaystyle operatorname {dist} (T({mathcal {M}}),{mathcal {S}})=sum _{min T({mathcal {M}})}sum _{sin {mathcal {S}}}(m-s)^{2}}     (3) dist robust ⁡ ( T ( M ) , S ) = ∑ m ∈ T ( M ) ∑ s ∈ S g ( ( m − s ) 2 ) {displaystyle operatorname {dist} _{operatorname {robust} }(T({mathcal {M}}),{mathcal {S}})=sum _{min T({mathcal {M}})}sum _{sin {mathcal {S}}}g((m-s)^{2})}     (4) μ i j = { 1 if point  m i  corresponds to point  s j 0 otherwise {displaystyle mu _{ij}=leftlbrace {egin{matrix}1&{ ext{if point }}m_{i}{ ext{ corresponds to point }}s_{j}\0&{ ext{otherwise}}end{matrix}} ight.}     (rpm.1) cost = ∑ j = 1 N ∑ i = 1 M μ i j ‖ s j − t − A m i ‖ 2 + g ( A ) − α ∑ j = 1 N ∑ i = 1 M μ i j {displaystyle operatorname {cost} =sum _{j=1}^{N}sum _{i=1}^{M}mu _{ij}lVert s_{j}-mathbf {t} -mathbf {A} m_{i} Vert ^{2}+g(mathbf {A} )-alpha sum _{j=1}^{N}sum _{i=1}^{M}mu _{ij}}     (rpm.2) μ j ^ = exp ⁡ ( β Q j ^ ) ∑ j = 1 J exp ⁡ ( β Q j ) {displaystyle mu _{hat {j}}={frac {exp {(eta Q_{hat {j}})}}{sum _{j=1}^{J}exp {(eta Q_{j})}}}}     (rpm.3) E ( μ ) = ∑ j = 1 N ∑ i = 0 M μ i j Q i j {displaystyle E(mu )=sum _{j=1}^{N}sum _{i=0}^{M}mu _{ij}Q_{ij}}     (rpm.4) K C ( x i , x j ) = ∫ K ( x , x i ) ⋅ K ( x , x j ) d x {displaystyle KC(x_{i},x_{j})=int K(x,x_{i})cdot K(x,x_{j})dx}     (kc.1) K C ( X ) = ∑ i ≠ j K C ( x i , x j ) = 2 ∑ i < j K C ( x i , x j ) {displaystyle KC({mathcal {X}})=sum _{i eq j}KC(x_{i},x_{j})=2sum _{i<j}KC(x_{i},x_{j})}     (kc.2) cost ⁡ ( S , M , θ ) = − ∑ m ∈ M ∑ s ∈ S K C ( s , T ( m , θ ) ) {displaystyle operatorname {cost} ({mathcal {S}},{mathcal {M}}, heta )=-sum _{min {mathcal {M}}}sum _{sin {mathcal {S}}}KC(s,T(m, heta ))}     (kc.3) K C ( S ∪ T ( M , θ ) ) = K C ( S ) + K C ( T ( M , θ ) ) − 2 cost ⁡ ( S , M , θ ) {displaystyle KC({mathcal {S}}cup T({mathcal {M}}, heta ))=KC({mathcal {S}})+KC(T({mathcal {M}}, heta ))-2operatorname {cost} ({mathcal {S}},{mathcal {M}}, heta )}     (kc.4) K C ( S ∪ T ( M , θ ) ) = C − 2 cost ⁡ ( S , M , θ ) {displaystyle KC({mathcal {S}}cup T({mathcal {M}}, heta ))=C-2operatorname {cost} ({mathcal {S}},{mathcal {M}}, heta )}     (kc.5) cost ⁡ ( S , M , θ ) = − N 2 ∫ x P M ⋅ P S   d x {displaystyle operatorname {cost} ({mathcal {S}},{mathcal {M}}, heta )=-N^{2}int _{x}P_{mathcal {M}}cdot P_{mathcal {S}}~dx}     (kc.6) p ( s ) = ∑ i = 1 M + 1 P ( i ) p ( s | i ) {displaystyle p(s)=sum _{i=1}^{M+1}P(i)p(s|i)}     (cpd.1) p ( s ) = w 1 N + ( 1 − w ) ∑ i = 1 M 1 M p ( s | i ) {displaystyle p(s)=w{frac {1}{N}}+(1-w)sum _{i=1}^{M}{frac {1}{M}}p(s|i)}     (cpd.2) E ( θ , σ 2 ) = − ∑ j = 1 N log ⁡ ∑ i = 1 M + 1 P ( i ) p ( s | i ) {displaystyle E( heta ,sigma ^{2})=-sum _{j=1}^{N}log sum _{i=1}^{M+1}P(i)p(s|i)}     (cpd.3) cost = − ∑ j = 1 N ∑ i = 1 M + 1 P old ( i | s j ) log ⁡ ( P new ( i ) p new ( s j | i ) ) {displaystyle operatorname {cost} =-sum _{j=1}^{N}sum _{i=1}^{M+1}P^{ ext{old}}(i|s_{j})log(P^{ ext{new}}(i)p^{ ext{new}}(s_{j}|i))}     (cpd.4) cost ⁡ ( θ , σ 2 ) = 1 2 σ 2 ∑ j = 1 N ∑ i = 1 M + 1 P old ( i | s j ) ‖ s j − T ( m i , θ ) ‖ 2 + N P D 2 log ⁡ σ 2 {displaystyle operatorname {cost} ( heta ,sigma ^{2})={frac {1}{2sigma ^{2}}}sum _{j=1}^{N}sum _{i=1}^{M+1}P^{ ext{old}}(i|s_{j})lVert s_{j}-T(m_{i}, heta ) Vert ^{2}+{frac {N_{mathbf {P} }D}{2}}log {sigma ^{2}}}     (cpd.5) P old ( i | s j ) = exp ⁡ ( − 1 2 σ old 2 ‖ s j − T ( m i , θ old ) ‖ 2 ) ∑ k = 1 M exp ⁡ ( − 1 2 σ old 2 ‖ s j − T ( m k , θ old ) ‖ 2 ) + ( 2 π σ 2 ) D 2 w 1 − w M N {displaystyle P^{ ext{old}}(i|s_{j})={frac {exp left(-{frac {1}{2sigma ^{{ ext{old}}2}}}lVert s_{j}-T(m_{i}, heta ^{ ext{old}}) Vert ^{2} ight)}{sum _{k=1}^{M}exp left(-{frac {1}{2sigma ^{{ ext{old}}2}}}lVert s_{j}-T(m_{k}, heta ^{ ext{old}}) Vert ^{2} ight)+(2pi sigma ^{2})^{frac {D}{2}}{frac {w}{1-w}}{frac {M}{N}}}}}     (cpd.6) In computer vision and pattern recognition, point set registration, also known as point matching, is the process of finding a spatial transformation that aligns two point sets. The purpose of finding such a transformation includes merging multiple data sets into a globally consistent model, and mapping a new measurement to a known data set to identify features or to estimate its pose. A point set may be raw data from 3D scanning or an array of rangefinders. For use in image processing and feature-based image registration, a point set may be a set of features obtained by feature extraction from an image, for example corner detection. Point set registration is used in optical character recognition, augmented realityand aligning data from magnetic resonance imaging with computer aided tomography scans. The problem may be summarized as follows:Let { M , S } {displaystyle lbrace {mathcal {M}},{mathcal {S}} brace } be two finite size point sets in a finite-dimensional real vector space R d {displaystyle mathbb {R} ^{d}} , which contain M {displaystyle M} and N {displaystyle N} points respectively. The problem is to find a transformation to be applied to the moving 'model' point set M {displaystyle {mathcal {M}}} such that the difference between M {displaystyle {mathcal {M}}} and the static 'scene' set S {displaystyle {mathcal {S}}} is minimized. In other words, a mapping from R d {displaystyle mathbb {R} ^{d}} to R d {displaystyle mathbb {R} ^{d}} is desired which yields the best alignment between the transformed 'model' set and the 'scene' set. The mapping may consist of a rigid or non-rigid transformation. The transformation model may be written as T {displaystyle T} where the transformed, registered model point set is: It is useful to define an optimization parameter θ {displaystyle heta } : such that it is clear that the optimizing algorithm adjusts θ {displaystyle heta } . Depending on the problem and number of dimensions, there may be more such parameters. The output of a point set registration algorithm is therefore the transformation parameter θ {displaystyle heta } of model T {displaystyle T} so that M {displaystyle {mathcal {M}}} is optimally aligned to S {displaystyle {mathcal {S}}} . In convergence, it is desired for the distance between the two point sets to reach a global minimum. This is difficult without exhausting all possible transformations, so a local minimum suffices. The distance function between a transformed model point set T ( M ) {displaystyle T({mathcal {M}})} and the scene point set S {displaystyle {mathcal {S}}} is given by some function dist {displaystyle operatorname {dist} } . A simple approach is to take the square of the Euclidean distance for every pair of points: Minimizing such a function in rigid registration is equivalent to solving a least squares problem. However, this function is sensitive to outlier data and consequently algorithms based on this function tend to be less robust against noisy data. A more robust formulation of the cost function uses some robust function g {displaystyle g} : Such a formulation is known as an M-estimator. The robust function g {displaystyle g} is chosen such that the local configuration of the point set is insensitive to distant points, hence making it robust against outliers and noise. Given two point sets, rigid registration yields a rigid transformation which maps one point set to the other. A rigid transformation is defined as a transformation that does not change the distance between any two points. Typically such a transformation consists of translation and rotation. In rare cases, the point set may also be mirrored. Given two point sets, non-rigid registration yields a non-rigid transformation which maps one point set to the other. Non-rigid transformations include affine transformations such as scaling and shear mapping. However, in the context of point set registration, non-rigid registration typically involves nonlinear transformation. If the eigenmodes of variation of the point set are known, the nonlinear transformation may be parametrized by the eigenvalues. A nonlinear transformation may also be parametrized as a thin plate spline.