# A Relationship between Spline-based Deformable Models and Weighted Graphs in Non-rigid Matc

A Relationship between Spline-based Deformable Models and Weighted Graphs in Non-rigid Matching

Anand Rangarajan Department of CISE Univ. of Florida Gainesville, FL Haili Chui Medical Imaging Group R2 Tech. Los Altos, CA Eric Mjolsness Machine Learning Group JPL Pasadena, CA

Abstract

Deformable models are central to non-rigid motion analysis, shape matching and non-rigid medical image registration. Spline-based deformations are a very popular class of parameterizations of deformable models and have been heavily used in multiple domains. In a somewhat separate sub-?eld, weighted graphs are a frequently used object parameterization. Graph matching using weighted graph object parameterizations ?nds application in a spectrum ranging from rigid pose estimation to deformable object recognition. Here, we demonstrate a hitherto unsuspected relationship between spline-based deformable models and weighted graphs. It turns out that spline parameterizations in the kernel representation can be used to construct equivalent weighted graphs. With this connection established, we envision a cross-fertilization between these two seemingly disparate sub-?elds of computer vision.

1. Introduction

Deformable models are very useful in domains such as articulated and non-rigid motion analysis [1], shape matching and recognition [15], deformable templates [25] and nonrigid medical image registration [19]. Depending on the task at hand, deformable models can be used to characterize object deformations or spatial mappings. In problem domains such as deformable object recognition, object deformations are important, whereas, in medical image registration, spatial deformations are paramount. In the past decade, spline-based deformable models have been widely utilized in situations calling for object and/or spatial deformations. In a somewhat separate sub-?eld, attributed, weighted, relational graphs have been the mainstay of object models for some time [10, 8]. Here, weighted graphs been used as object representations in problem domains such as pose estimation [8] and model matching [17, 4]. Since graphs easily encode rigid invariants (rotation, translation), they are 1

particularly useful in rigid matching situations such as pose estimation. In addition, graphs have been pressed into service in non-rigid matching domains as well [12, 2]. The need for modeling non-rigid deformations arises for different reasons in different domains. In character recognition, spline models are routinely constructed to model the objects (characters). Recognition is carried out by evaluating a distance measure between the spline models of the stored and incoming characters [15]. In medical image registration, thin-plate splines [23] are routinely used to characterize spatial deformations. Non-rigid registration is achieved by solving an associated (spline) regression problem [6]. However, a neat divide between using object deformation models in recognition and spatial deformation models in registration is not forthcoming. Spatial and object deformations have been used in recognition [3] and in registration [24, 20] respectively. Turning to graph representations of objects, we ?nd recognition and pose estimation problems cast as weighted graph matching (WGM) [2, 8]. The notorious correspondence problem raises its head here with most graph matching problems requiring that we solve for vertex permutations or closely related parameterizations [10]. In contrast to the earlier spline parameterization divide between object and spatial deformations, there is no such obvious conceptual divide here. Our primary objective in this paper is to build a bridge between spline-based deformable models and weighted graphs for non-rigid matching. We begin with a spline parameterized non-rigid matching problem. In particular, we leave open the choice of the spline kernel to be used. Regardless of the particular choice of kernel, splines are used to characterize the spatial deformation between two pointsets. In contrast to many previous approaches, we do not assume that the point-set is structured (e.g. curve in 2D or surface in 3D). Consequently, the non-rigid problem is set up to solve for the spline parameters and the correspondences between the point-sets [3, 7]. Next, we show that under certain circumstances, the non-rigid matching problem

can be reduced to a pure correspondence problem, by eliminating the spline parameters as a function of the correspondences [26, 27]. Once this is done, it is easy to show that the resulting correspondence problem can be interpreted as WGM with one of the graphs being directly related to the spline kernel. We have shown that weighted graph matching emerges from a spline parameterized non-rigid matching problem. This relationship is exciting because it opens the door to a cross-fertilization between these two seemingly disparate sub-?elds. With this connection established, it should be possible to ?esh out deeper relationships and perhaps even create a new super-framework with splinebased models and weighted graphs as its proper subsets.

spatial deformation. While the fourth issue of object parameterization is obviously important, it turns out that it is easier to show the intimate relationship between splinebased deformable models and weighted graphs by only considering these three issues. In establishing the relationship, we show that spline-based spatial deformations give way to graph-based object representations which is an interesting duality. Given the feature point-sets and ? , the non-rigid deformation is obtained by minimizing the following objective function:

?

×?? ? ? ? ?

? ?? ?

?

·

?

?

(1)

2 Review

The present work closely follows the development in [27]. However, the concerns in [27] are different and unrelated to WGM. Since previous work relating spline-based deformations to weighted graphs is rare, we instead focus on previous work in each of the above sub-?elds that is relevant to our synthesis. First, it should be mentioned that there is an enormous literature on intensity-based non-rigid matching [5] which is unrelated to our synthesis objective. We mention in passing that intensity-based methods avoid the correspondence problem (but typically require brightness constancy) and hence are not related to graph matching methods. We have already mentioned approaches that match pointsets [16, 11, 9, 7, 3]. Non-rigid matching methods run the gamut of also matching lines [4], curves [15, 20] and surfaces [21, 13, 22]. Non-rigid matching using graphs are less common [12, 2] except for the recent resurgence in using medial axis graph representations in matching [18, 14]. Insofar as we restrict focus to feature-based methods, the concerns are common. Whether splines or graphs are used, feature-based methods have to deal with some/all of the issues of i) rigid pose, ii) correspondence, iii) non-rigid spatial deformation and iv) object parameterization. Splinebased methods are more concerned with issues i) and one of iii) or iv). Graph-based methods are more concerned with issues ii) and iv). In the rest of this work, we attempt to relate these two approaches in the context of issues i) - iv).

In (1), we seek to recover the non-rigid mapping function . The ?rst term in (1) is a least-squares distance between corresponding points in and ? . Note that each and ? consists of the point coordinates in 2D or in 3D. The operator ? in the second term of (1) is a regularization operator. Different choices of ? result in different choices of splines. For instance, if ? is the Laplacian operator (in 2D or in 3D), the result is the familiar thin-plate spline (TPS) [6, 23]. If ? consists of a certain in?nite series of derivative operators, then it can be shown to correspond to the Gaussian radial basis function spline [27]. Irrespective of the chosen operator, the second term imposes a smoothness constraint on the entire space as opposed to the ?rst term which is a least-squares error term on the points alone. The parameter is a regularization parameter. Also noteworthy is that comprises not only the non-rigid spatial deformation but the rigid pose parameters as well since the spline in (1) is not supplemented by a separate rigid pose parameterization. The objective function in (1) is only valid when the feature point-sets are labeled and correspondences known. We now augment the objective by including the correspondences as unknown variables.

?

? ?

?

?

?

? ?

? ?? ?

?

·

?

?

(2)

In (2), is an unknown permutation which is required to and ? into correspondence. An bring the point-sets equivalent way of writing the objective in (2) is

? ?

3 Deriving the relationship

We begin with a non-rigid spline-based feature matching setup. Assume that we have two sets of unlabeled features and ? in 2D or in 3D. As mentioned at the end of Section 2, there are four important issues in non-rigid matching. In the feature matching problem considered here, we focus mainly on the issues of pose, correspondence and non-rigid 2

?

??

?? ??

? ?

? ?

? ??

·

?

?

??

?? ??

? ?

?

?

(3)

In (3), ? is a zero-one matrix with the property that feature in is matched to feature in ? if and only if ? ?. Since, one-to-one correspondence is desirable, we have the

? ? ? and ? [10]. The paconstraints ?? ?? rameter ? ? controls the number of null feature matches and is a robustness parameter. We prefer the formulation in (3) over the one in (2) because it is more amenable to algebraic manipulation. In summary, the objective function in (3) includes pose (via ), correspondence (via ? ) and nonrigid spatial deformations (via ) and does not impose any object model (since the point-sets are unstructured).

??

??

then a way to understand this constraint is to think of ? as a template which is being deformed and as data. In this case, may have many noise points that have no counterparts in ? but each point in ? has a corresponding point in . In other words, we do not allow model occlusion but we do allow noisy “extra” data features. After this simpli?cation, we may algebraically modify the objective function in (5) to

? ?

3.1 Moving to the kernel representation

A well known relationship exists between the regularization operator ? and its corresponding spline kernel [23]. We brie?y describe this relationship. Since the regularization operator is deemed to act on the entire space ( ? or ? ), it is straightforward to switch from the operatorspace representation to the kernel representation. This is accomplished by solving the Euler-Lagrange equations for (1) with no forcing data term. The solution to the EulerLagrange equation—called the Green’s function—allows us to write in terms of the corresponding spline kernel ? .

? ?

?

?

??

??

?

??

?

? ?

?

?

??

? ?

?? ?

??

?

? ? ?

??

?

?

?? ??

·

?

?

?

?

?

?

·

The objective function in (6) makes explicit the fact that the . This is valid only when counterpart of ? is ??? ? “all of ? ” is present in . We now switch to matrix notation and rewrite (6).

? ?

?

trace?
? ?
?

(6)

?

?

?

??

??

? ?

? ?diag?

?

·

? ?? ? ? ?

??

?

trace?
? ?
?

?

(4)

·trace

?

? ?? ? ?

?

(7)

A few clari?cations are required for (4). In (4), ? is any spatial location (in 2D or in 3D) and ? is a point in ? . The coef?cients
are unknown and require the data in order to be speci?ed. The scalar kernel function ? ??? is obtained from the Green’s function of (1). For more details, please see [23]. Once the Green’s function (and therefore the kernel as well) are speci?ed, we may transition from the operator representation to the kernel representation.

? ?
?

??

?? ??

? ?

?

?

?

?? ?

? ? ?

?? ??

? ?

?

·

trace?
? ?
? ? ?

?

(5)

In the ?rst term of (5), it should be understood that a separate spline is required for each dimension of (2D or 3D). Note that the second term of (5) is purely a relational term on ? and not on the entire space: the ? ?th entry of matrix ? is ? ? ? ? ? ? ?. We now make a technical simpli?cation that facilitates the demonstration of the relationship between splines and weighted graphs. When the one-to-one correspondence constraints were added in (3), we allowed for outliers in both feature point-sets. Instead, we modify the constraint ?? ?? ? to ?. This has the effect of ?? ?? demanding that every point in ? has to have a counterpart in but not vice versa. If the task were object recognition,

?

?

In (7), is ?? ? , ? is ?? ? ?? , ? is ?? ? ?? , and
is ?? ? where is the dimensionality of the point-sets (usually 2 or 3 but may be augmented when using homogeneous coordinates). The ?rst term uses a Frobenius norm but is equivalent to the vector norms used earlier in (6). At this juncture, we feel that a capsule summary of the derivation of the relationship is in order. We began with a non-rigid feature matching problem using a spline parameterized spatial deformation model. Since the point-to-point correspondences are unknown, they were also included in the objective function. After some simpli?cations and algebraic manipulations, we have an objective function de?ned w.r.t. the spline coef?cients
and the correspondences ? . The actual choice of spline is buried in the kernel ? . The next step involves eliminating the spline coef?cients
from the objective function in (7) which is straightforward since (7) is a standard least-squares cost function w.r.t.
but not on ? since the latter is binary-valued. After
is eliminated, we interpret the resulting objective function as a WGM problem. The de?nitions of the weighted graphs follows naturally from the interpretation. Eliminating the spline coef?cients from (7) is straightforward. We differentiate (7) w.r.t.
and use the ?rst-order Karush-Kuhn-Tucker conditions. This is valid provided ? is a positive de?nite matrix

3

?

? ? ?? ? ? ?
? · ?
?
?? · ? ?? ? ?

?

?

(8)

Having obtained a closed-form solution for
(which is the optimal solution), we substitute it in (7) and eliminate
. After some algebraic manipulation, we get

?? ? ?

??

trace?? ? ?? ?? · ? ??? ? ? ? trace ? ?? · ? ??? ? ? ??

? ??(9)

In the remainder of this section, we interpret (9) as a WGM problem with the adjacency matrix of one graph being ?. ?? · ? ??? and that of the other being ?

3.2 Weighted graph matching

As mentioned previously, weighted graph matching is usually associated with rigid matching [8]. This is mainly due to the rigid invariants encoded in the weighted graphs. For example, the set of inter-point Euclidean distances is invariant to the overall rotation and translation of the point-set. And the set of angles culled from point triples is invariant to similarity transformations of the point-set. Unfortunately, invariants come at a price. Solving for vertex permutations in WGM is usually a much harder problem (NPcomplete) [10] than the bipartite matching problem in (3) which has several polynomial-time solutions [7]. Recently, there has been some interest in using graph matching approaches in non-rigid matching situations [18, 14]. While these approaches are restricted to using medial representations of the underlying data, there is no a priori reason for such a limitation. Regardless of the origin of the weighted graphs, a WGM problem can be written as [10]

? ??

A pure correspondence problem results which has been interpreted as WGM. Note that the smoothness constraint imposed by the spline (in the form of the operator ?) forces nearby points to behave cohesively. When the spline coef?cients are eliminated, the spline nevertheless leaves its imprint on the problem in the form of a weighted graph ? . The links in ? are directly related to the spline kernel. Spatial smoothness of the deformation (emphasized by the spline representation) gives way to point correlation (emphasized by the graph representation). We examine these issues in greater, quantitative detail, for a particular spline— the thin-plate spline (TPS).

4 Visualizing spline graphs

The TPS kernel ? ??? ?? ?? ? in 2D and is not positive de?nite. Wahba [23] explains the notion of conditional positive de?niteness and carries out the analysis for the TPS. Essentially, the TPS kernel becomes positive de?nite when con?ned to a non-af?ne subspace. In the operator formulation, the TPS energy is the square of the Laplacian integrated over the entire space. The Laplacian operator annihilates constants and linear functions of spatial coordinates. In 1D, the TPS results in the familiar cubic spline. In 2D, the TPS results in the ?? ?? ? kernel as noted above. And in 2D, constants and af?ne terms are annihilated by the TPS energy. Positive de?niteness is achieved by restricting the TPS to a non-af?ne subspace. A QR decomposition is used to represent the point coordinate vectors in its af?ne and non-af?ne subspace. The non-af?ne portion of the decomposition is culled and the kernel projected into that subspace. For more details, please see [23]. There are no complications resulting from the correspondence variable because we have already taken care to not have outliers in both point-sets. The WGM objective now has ? ?? ??? ???? ?? · ? ??? ?? with ? ?. ? ? In the above, ? ?? ?? ?? with ? written in the homogeneous coordinate notation. The dimensions of ?? and ?? are ?? ? ? and ?? ? ??? ? ?? respectively. Since af?ne subspaces are removed from ? , we also remove the centroid of prior to computing . In Figure 1, we show both ? and . The graph is visualized after removing its center of mass since that leaves the problem unchanged. The graph ? is shown for decreasing values of . Please note that and ? are topologically similar only at large values of . As is decreased, the TPS graph switches from emphasizing long range connections to nearest neighbor connections. This is true for both templates—the Chinese character and the ?sh ? emphasizes long range connecpattern. The graph tions over short range connections because the link weights are larger for long range connections. When is large, ? ?? ?? which is an af?ne invariant [23]. We have no? 4

??

?

?

? ?

?trace ? ? ? ?

?

(10) In (10), ? and are the adjacency matrices formed from ? and respectively. The usual simplex constraints apply to ? in this case as well. Weighted graph matching is a special case of the quadratic assignment problem (QAP) [26]. Once the link between spline-based deformable models and WGM is established, other equivalent forms of WGM (or to QAP) can be used if appropriate. Examine (9) and (10). It should be straightforward to ? . The associate ? with ?? · ? ??? and with ? ? and is asymmetry between the adjacency matrices due to the fact that ? is being deformed whereas is held ?xed. Graph ? is also dependent on the regularization parameter . When is small, ? ? ?? and at large , ? ? . In contrast, the adjacency matrix of point-set is unaffected by . Finally, the choice of the spline affects the kernel ? which in turn affects the adjacency matrix of point-set ? . We have shown that a weighted graph matching emerges from a spline parameterized non-rigid matching problem when the spline coef?cients are eliminated from the latter.

ticed that ? ?? ?? ? ????? ? ?? ?? ? ? ??? ? ? ? also emphasizes long range connections, thereby explaining . To show that this phenomenon is not its similarity to isolated, we depict the graphs for a number of hand-drawn characters in Figure 2. All these graphs are shown at a small value of . Note the absence of long range connections in virtually all the graphs. The fact that point-set warping does not appreciably change the topology (at least for small warps) is shown in Figure 3. We created a point-set and show its ? in Figure 3. Then, we warped the point-set using progressively larger TPS warps. For each new point-set, we display its ? graph. Visual inspection reveals that the graph topologies are not appreciably different. More work is required to understand the ways these graphs change under warping.

and ? ? ? ? . Note that the two graphs are invariant to rigid transformations of the pointsets ? and but are not invariant under scale transformations. Also, assume that ? is deformed as before but under the action of a new transformation.

?

??

? ?×

??

×?

·

?

? ×? ? ?

(11)

where × is a global scale parameter and ? is a local “graph ?ow” displacement ?eld. After setting up the two graph representations and displacement ?eld transformation, consider the following objective function:

? ? ? ?? ?

? × ??

? ?

?

? ?×

?? ?

(12)

5 Discussion

The equivalence between a spline spatial transformation model ? and weighted graph object models ? is the main contribution of this paper. We have empirically observed that the graph ? starts becoming signi?cantly different from as is decreased. Short range nearest neighbor relations are preferred over long range connections in ? as is lowered. This suggests a certain action on the algorithmic front. If this analysis holds, it makes more sense to computationally warp the point-set ? and “reset” the problem rather than stay with the original point-sets. After a certain correspondence is obtained, a new point-set ? can be obtained using a heavily regularized TPS. In this way, we keep ? and similar (at least for small warps). And is always rather large since the point-set ? is being continuously regenerated rather than held ?xed. We speculate that this strategy could improve the performance of recent approaches such as [3, 7]. We have devoted much space in covering the transition from spline-based deformable models to weighted graphs. What about the opposite direction? Is it possible to formulate WGM objectives and show equivalence to a corresponding spline. We think that this reverse direction is very dif?cult to establish. However, there is one intriguing possibility which is available to us. Our analysis of the difference between short range and long range connections suggests the possibility of and their impact on ? and a new formulation. The graph is a very simple graph because the spline-based deformable model does not operat all. Only the point-set ? is afate on the point-set fected by the spline. Consequently, the connectivity pattern ?. in is quite basic resulting from the outer product A way to directly involve the inter-relationships between the points in both point-sets can be achieved by formulating the warping in a link space and not in the point space. Assume that we have two graphs with adjacency matrix entries 5

with the double simplex constraints on ? as before. Equation (12) relates the two graphs using a correspondence matrix and also through a new displacement ?eld ? . From an algorithmic standpoint, when ?× ? ? are held ?xed, we have a WGM problem on ? and when ? is held ?xed, we have a standard least-squares problem on ?× ? ?. Our new objective function also affords the possibility of correlated outlier treatment. Rather than continue having different sized point-sets leading to different sized graphs, the optimization on (12) could ?nd optimal point locations in one point-set corresponding to the outliers in the other and viceversa. Once again, this could be set up in a standard leastsquares framework but with the crucial difference being that the point-sets and the graphs would be of equal size ? . In point-set ? , it would be understood that the ?rst ?? points are the actual points and the remaining ? ? ?? points are new point locations in search of outlier counterparts in . And would have its ?rst ?? points be identical to the actual points and the remaining ? ? ?? points be new point locations in search of outlier counterparts in ? . The size of ? is an unresolved issue but far simpler than having to estimate outlier parameters such as ?. The principal dif?culty with objective functions such as (12) lies in designing suitable optimization algorithms. Solving WGM problems during each phase of an alternating algorithm is expensive (and fraught with local minima issues) and smells wrong. However, approximate reductions of WGM to linear assignment (for the correspondence phase) as explored in [10, 3] are obviously possible. Since initial conditions are readily available from the previous entry into the WGM phase of the alternation, this approach is viable. We think that such an approach has not been previously considered due to the perception (somewhat widely held) that it would be impractical. We wish to point out that practical alternatives are available and worth considering. Finally, all four aspects of non-rigid warping—object ?, pose ?×?, warps ?? ? and correspondence models ? ? ?? ?—are contained in (12).

6 Conclusion

We have shown the emergence of weighted graph matching from a spline-based non-rigid matching problem. In particular, the spatial deformation spline model was shown to be equivalent to a graph object model in weighted graph matching. This connection is exciting because it relates two sub-?elds and we are not aware of other work drawing attention to this connection. We hope that the demonstration of this relationship will result in new computational and algorithmic insights stemming from a cross-fertilization of hitherto unrelated sub-?elds.

[11] S. Gold, A. Rangarajan, C. P. Lu, S. Pappu, and E. Mjolsness. New algorithms for 2-D and 3-D point matching: pose estimation and correspondence. Pattern Recognition, 31(8):1019–1031, 1998. [12] M. Lades, J. C. Vorbruggen, J. Buhmann, J. Lange, C. von der Malsburg, R. P. Wurtz, and W. Konen. Distortion invariant object recognition in the dynamic–link architecture. IEEE Trans. Computers, 42(3):300–311, Mar. 1993. [13] D. Metaxas, E. Koh, and N. I. Badler. Multi-level shape representation using global deformations and locally adaptive ?nite elements. Intl. J. Computer Vision, 25(1):49–61, 1997. [14] M. Pelillo, K. Siddiqi, and S. Zucker. Matching hierarchical structures using association graphs. IEEE Trans. Patt. Anal. Mach. Intell., 21(11):1105–1120, 1999. [15] M. Revow, C. K. I. Williams, and G. Hinton. Using generative models for handwritten digit recognition. IEEE Trans. Patt. Anal. Mach. Intell., 18(6):592–606, June 1996. [16] S. Sclaroff and A. P. Pentland. Modal matching for correspondence and recognition. IEEE Trans. Patt. Anal. Mach. Intell., 17(6):545–561, Jun. 1995. [17] L. G. Shapiro and R. M. Haralick. Structural descriptions and inexact matching. IEEE Trans. Patt. Anal. Mach. Intell., 3(9):504–519, Sept. 1981. [18] D. Sharvit, J. Chan, H. Tek, and B. B. Kimia. Symmetrybased indexing of image databases. J. of Visual Communication and Image Representation, 9(4):366–380, 1998. [19] R. Szeliski and S. Lavallee. Matching 3D anatomical surfaces with non-rigid deformations using octree splines. Intl. J. Computer Vision, 18:171–186, 1996. [20] H. Tagare. Shape-based nonrigid correspondence with application to heart motion analysis. IEEE Transactions on Medical Imaging, 18(7):570–579, July 1999. [21] P. Thompson and A. W. Toga. A surface-based technique for warping three-dimensional images of the brain. IEEE Trans. Med. Imag., 5(4):402–417, August 1996. [22] M. Vaillant and C. Davatzikos. Hierarchical matching of cortical features for deformable brain image registration. In Information Processing in Medical Imaging (IPMI ’99), volume 1613, pages 182–195. Springer-Verlag, 1999. [23] G. Wahba. Spline models for observational data. SIAM, Philadelphia, PA, 1990. [24] Y. Wang and L. H. Staib. Boundary ?nding with prior shape and smoothness models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(7):738–743, July 2000. [25] A. Yuille and P. Hallinan. Deformable templates. In A. Blake and A. Yuille, editors, Active Vision. MIT Press, Cambridge, MA, 1992. [26] A. L. Yuille. Generalized deformable models, statistical physics, and matching problems. Neural Computation, 2(1):1–24, 1990. [27] A. L. Yuille and N. M. Grzywacz. A mathematical analysis of the motion coherence theory. Intl. J. Computer Vision, 3(2):155–175, June 1989.

Acknowledgments

This work is supported by NSF IIS 9906081 to A.R.

References

[1] J. Aggarwal, Q. Cai, W. Liao, and B. Sabata. Articulated and elastic non-rigid motion: A review. In Proc. IEEE Workshop on Motion of Non-Rigid and Articulated Objects, pages 16– 22, 1994. [2] Y. Amit and A. Kong. Graphical templates for model recognition. IEEE Trans. Patt. Anal. Mach. Intell., 18(4):225–236, 1996. [3] S. Belongie, J. Malik, and J. Puzicha. Matching shapes. In Intl. Conf. Computer Vision (ICCV). IEEE Press, 2001. (accepted). [4] R. Bergevin and M. D. Levine. Generic object recognition: Building and matching coarse descriptions from line drawings. IEEE Trans. Patt. Anal. Mach. Intell., 15(1):19–36, Jan. 1993. [5] M. Black and A. Jepson. Estimating optical ?ow in segmented images using variable-order parametric models and local deformations. IEEE Trans. Patt. Anal. Mach. Intell., 18(10):972–986, 1996. [6] F. L. Bookstein. Principal warps: Thin-plate splines and the decomposition of deformations. IEEE Trans. Patt. Anal. Mach. Intell., 11(6):567–585, June 1989. [7] H. Chui and A. Rangarajan. A new algorithm for non-rigid point matching. In IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), volume 2, pages 44–51, 2000. [8] A. D. J. Cross and E. R. Hancock. Graph matching with a dual-step EM algorithm. IEEE Trans. Patt. Anal. Mach. Intell., 20(11):1236–1253, 1998. [9] N. Duta, A. K. Jain, and M.P. Dubuisson-Jolly. Learning 2D shape models. In IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), volume 2, pages 8–14, 1999. [10] S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. IEEE Trans. Patt. Anal. Mach. Intell., 18(4):377–388, 1996.

6

YYT Graph

TPS Graph

TPS Graph

TPS Graph

YY Graph

T

TPS Graph

TPS Graph

TPS Graph

YYT Graph

TPS Graph

TPS Graph

TPS Graph

YYT Graph

TPS Graph

TPS Graph

TPS Graph

? graph. The entries with Figure 1: Two graph representations. First Row: the graphs of the ?sh pattern. Leftmost: ? relatively large absolute values are shown as links. From second left to rightmost: TPS graph with gradually reduced values of . Second Row: the graphs of a warped ?sh pattern. Third Row: the graphs of a Chinese character. Fourth Row: the graphs of a warped Chinese character.

7

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

TPS Graph

Figure 2: More TPS graphs. All the graphs shown here are TPS graphs at a small value of

Figure 3: On the top an original point-set is shown along with its graph depicted for a certain threshold. Below, we show four different thin-plate warped point-sets and their associated graphs. The warping increases as you go from left to right. Note the increased distortion in the topology going from left to right. The same threshold was used for all the graphs.

8