DOC PREVIEW
Stanford CS 468 - Point Sets up to Rigid Transformations are Determined

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Point Sets up to Rigid Transformations are Determined by the Distribution of their Pairwise DistancesDaniel ChenSurvey of results of M. Boutin and G. KemperOutline•Motivation•Preliminaries•Folklore Lemma•Main Result•Computation•Extensions and Open ProblemsMotivation•Shape Distributions of [osada]•Distribution of different functions on randomly selected points considered.•Different dissimilarity measures between distributions also considered.Motivation•Comparing the distribution of pairwise distances w.r.t L1 norm appears to be a good classifier.•This paper provides some reasoning on why this might be the case: When the distribution of pairwise distances are identical, then the points in general position are the same up to a rigid transformation.Preliminaries•General Position•Rigid Transformation•Distribution of Pairwise Distances•Reconstructibility from Pairwise didstancesGeneral Position•As defined by Matousek:•Set of points not in general position has measure zero.Let a set of n points in Rdbe specified by a vector t =(t1,t2, . . . , tm) form = dn. Then, a general position condition is a condition that can be expressedas!ipi(t) != 0 for a countable number of polynomials pi.Rigid Transformation•Definition:Let p be a point in Rm. Then a rigid transformation is a function R : Rm→Rmthat can be written as R(p)=Mp + T where M is an orthogonal m-by-mmatrix and T is a column vector in Rm.Pairwise Distances•Distribution:•Reconstructibility:Given a set of points P , let the distribution of pairwise distances d(P ) bethe multiset {||pi− pj||}i<j.We say that p1, . . . , pn∈ Rmis reconstructible from pairwise distances if forevery q1, . . . , qn∈ Rmwith the same distribution of pairwise distances, thereexists a rigid transformation R and a permutation π of {1, . . . , n}, such thatP (pi)=qπ(i)for every i ∈ 1, . . . , n.Folklore Lemma•Tricky to work with rigid transformations directly.•Compare distance matrices instead.•Folklore Lemma:Let p1, . . . , pnand q1, . . . , qnbe points in Rm. If ||pi− pj|| = ||qi− qj||for every i, j in 1, . . . , n, then there exists a rigid transformation R such thatR(pi)=qifor all i.Folklore Lemma•Proof:Let xi= pi− pnand yi= qi− qnfor i =1, . . . , n. We claim that "xi,xj# ="yi,yj# for all i, j. To see this, we have the following calculation:"xi,xj# = "pi− pn,pj− pn#="pi− pn,pi− pn# + "pj− pn,pj− pn#−"pi− pj,pi− pj#2=||pi− pn|| + ||pj− pn|| − ||pi− pj||2=||qi− qn|| + ||qj− qn|| − ||qi− qj||2="qi− qn,qi− qn# + "qj− qn,qj− qn#−"qi− qj,qi− qj#2= "qi− qn,qj− qn# = "yi,yj#Now, let X =[x1, · · · ,xn] and Y =[y1, · · · ,yn]. We have shown abovethat XTX = YTY . Now, XTX is symmetric and positive semidefinite, andhence can be written as QΛQTfor an orthogonal Q and a non-negative diagonalmatrix Λ. Since Λ, is non-negative, we can write XTX = YTY = QΛ1/2Λ1/2QT.Therefore, using the singular value decomposition, we can write X as UXΛ1/2QTand Y as UYΛ1/2QTfor orthogonal UXand UY. Then, we can write Y = MXfor orthogonal M = UYUTX. Moreover, it is easy to verify that Mxi= yifor i =1, . . . , n. To finish the proof, we note that M(pi− pn)=qi− qnorqi= Mpi+ qn− Mpnso there is a rigid transformation from pito qiwith theorthogonal matrix M and translation vector qn− Mpn.Digression: Counterexample•1D Counterexample:•2D Counterexample:P = {0, 1, 4, 10, 12, 17} Q = {0, 1, 8, 11, 13, 17}It can be verified that the distribution of distances is the multiset:d(P )=d(Q)={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17}Main Idea•With Folklore Lemma in mind, show that if two point sets have the same distribution of pairwise distances, they have the same distance matrices up to a relabeling of the points.Some Notation•Convention:•Corollary:Let P = {p1, . . . , pn} be a labeled set of n points. Then we let dP: P → Rbe defined as dP({i, j})=||pi− pj||2.If n-point configurations P and Q have the same distribution of distances,then there exists a permutation φ of P such that dP(φ({i, j})) = dQ({i, j}) forall {i, j} ∈ P.A Weaker Result•Proof:Let P be a configuration of n points.Then, there exists neighborhoods of pisuch that if Q if a configuration of n points with qiin the neighborhood of piand having the same distribution of distances as P , then P and Q are the sameup to a rigid transformation and a relabeling of the points.Suppose for the purpose of contradiction that there exists a sequence ofconfigurations {Qk}∞k=1converging to P such that none of Qkcan be mappedto P via rigid transformation and relabeling, but there exists a sequence ofpermutations {φk}∞k=1such that dP(φk({i, j})) = dQk({i, j}). Since there arefinitely many permutations φk, we can pick φ1, for instance, and let {Rl}∞l=1bethe subsequence of {Qk}∞k=1where φk= φ1. Then, taking the limit | →∞ , wehave dP(φ1({i, j})) = liml→∞dRl({i, j}). Since {Rl}∞l=1converges to P , we thenhave dP(φ1({i, j})) = dP({i, j}). But then, we have dP({i, j})=dQk({i, j}) andby the Folklore Lemma, there is a rigid transformation from P to Qk, so wehave a contradiction.Relabelings•Corollary:•We want to show most point sets with the same distribution of distances have a relabeling.A permutation φ of P is a relabeling if there exists a permutation π of{1, . . . , n} such that φ({i, j})={π(i), π(j)}.If there exists a relabeling φ of P such that dP(φ({i, j})) = dQ({i, j}), thenthere is a permutation π of {1, . . . , n} such that pπ(1 ), . . . , pπ(n )has the samedistance matrix as q1, . . . qn, and therefore, by the Folklore Lemma, there is arigid transformation from pπ(1 ), . . . , pπ(n )to q1, . . . qn.Key Lemma•Proof:Suppose n != 4. Then a permutation φ of P is a relabeling if and only if forall pairwise distinct indices i, j, k we have φ({i, j}) ∩ φ({i, k}) != ∅.For every n ≤ 3, every φ is a relabeling and φ({i, j}) ∩ φ({i, k}) #= ∅. There-fore, we may assume that n ≥ 5. The only if part of the statement is clear bythe definition of a relabeling, so we will show the if direction.Suppose we have φ a permutation of P such that for all pairwise distinctindices i, j, k we have φ({i, j}) ∩ φ({i, k}) #= ∅. We note that since φ is apermutation, the intersection must then contain only one element. Then, weargue that for i, j, k, l pairwise distinct, φ({i, j}) ∩ φ({i, k}) ∩ φ({i, l}) #= ∅.Suppose otherwise. Then, we can


View Full Document

Stanford CS 468 - Point Sets up to Rigid Transformations are Determined

Download Point Sets up to Rigid Transformations are Determined
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Point Sets up to Rigid Transformations are Determined and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Point Sets up to Rigid Transformations are Determined 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?