November 25, 2003 Lecture 23: Geometric Pattern Matching1Geometric Pattern MatchingPiotr IndykNovember 25, 2003 Lecture 23: Geometric Pattern Matching2Face RecognitionNovember 25, 2003 Lecture 23: Geometric Pattern Matching3Matching in a SceneNovember 25, 2003 Lecture 23: Geometric Pattern Matching4Formalization: Shapes• Today: – A shape is a set A of points in R2– |A|=n• In general, A could consist of segments etc.November 25, 2003 Lecture 23: Geometric Pattern Matching5Formalization: (Dis)similarity• Hausdorff distance– DH(A,B)=maxa∈Aminb∈B||a-b||– H(A,B)=max[ DH(A,B), DH(B,A) ]• Earth-Mover Distance– Minimum cost of a one-to-one matching between A and B– EMD(A,B)=minf:A B, a∈A||a-f(a)||, f is 1:1• Bottleneck matching– BM(A,B)= minf:A B, maxa∈A||a-f(a)||, f is 1:1November 25, 2003 Lecture 23: Geometric Pattern Matching6Computing H(A,B)• Given A,B, how fast can we compute H(A,B) ?– We will compute DH(A,B)– Construct a Voronoi diagram V for B– Construct a point location structure for V– For each a in A, find its NN in B• Total time: O(n log n)November 25, 2003 Lecture 23: Geometric Pattern Matching7Approximate Hausdorff• Assume we just want an algorithm that:– If DH(A,B) r, answers YES– If DH(A,B) (1+ ε)r, answers NO• Algorithm:– Impose a grid with cell diameter εr– For each b∈B, mark all cells within distance r from b– For each a∈A, check if a’s cell is marked • Time: O(n/ε2)November 25, 2003 Lecture 23: Geometric Pattern Matching8Alignment• In general, A and B are not aligned• So, in general, we want– DHT(A,B)=mint∈TDH(t(A),B) , where• T=translations• T=translations and rotations• …– Same for H• How can we compute it ?November 25, 2003 Lecture 23: Geometric Pattern Matching9Decision Problem• Again, focus on if DHT(A,B) r• For a∈A, defineT(a)={ t: ∃b∈B ||t(a)-b|| r }• DHT(A,B) r iffa∈AT(a) is non-emptyNovember 25, 2003 Lecture 23: Geometric Pattern Matching10ExampleNovember 25, 2003 Lecture 23: Geometric Pattern Matching11Algorithm• Compute the arrangement of all disks• Check for non-emptiness• Analysis:– Number of disks: n2– Size of the arrangement: O(n4)– Can compute the arrangement in time O(n4)– Total time: O(n4)• Can be improved to O(n3 log n) [Chew,Goodrich,Huttenlocher,Kedem,Kleinberg,Kravets’93]November 25, 2003 Lecture 23: Geometric Pattern Matching12Running time• Running time pretty high• Can we speed it up?• A (1+ε)-approximate algorithm for DHT:– Impose a grid will pixel diameter εr– Approximate each disk by O(1/ε2) cells– Each T(a) is approximated by O(n/ε2) cells– Need to check intersection of n T(a)’s– O(n2/ε2) timeNovember 25, 2003 Lecture 23: Geometric Pattern Matching13Approximate Algorithm for H()• Reference point: a point r(A) such that if we set t=r(B)-r(A) , thenH( t(A), B ) c HT(A,B)• Note that t transforms r(A) into r(B)• This will give us a c-approximate algorithm with time O(n log n)November 25, 2003 Lecture 23: Geometric Pattern Matching14Constructing a Ref Point• r(A)=(mina∈Aax, mina∈Aay)• Introduced in [Alt, Behrends, Blomer’91]• Improved in [Aichholzer, Alt, Rote’94]r(A)November 25, 2003 Lecture 23: Geometric Pattern Matching15TheoremTheorem: r(A) is a reference point with c=1+√2Proof:• Consider t such that H(t(A),B)=HT(A,B)• What is |mina∈At(a)x- minb∈Bbx| ?• It is at most HT(A,B)• Same for |mina∈At(a)y- minb∈Bby|• Thus, we can translate t(A) by a vector of length √2 HT(A,B) , so that its reference point is aligned with r(B)November 25, 2003 Lecture 23: Geometric Pattern Matching16The (1+√2) Factor is Tight(for this reference point)November 25, 2003 Lecture 23: Geometric Pattern Matching17Exact Matching• Check if DHT(A,B)=0– Can modify the algorithm to allow small error– Technique used in practiceNovember 25, 2003 Lecture 23: Geometric Pattern Matching18Algorithm• Take any pair a,a’∈A, let r=||a-a’||• Find all pairs b,b’∈B such that ||b-b’||=r• For all such pairs– Compute t that transforms (a,a’) into (b,b’)– Check if t(A) ⊆ BNovember 25, 2003 Lecture 23: Geometric Pattern Matching19Analysis• Choosing a,a’ : constant time• Enumerating b,b’ : O(n2) time• Checking match: O(n P) , where P is the number of pairs b,b’∈B s.t. ||b-b’||=r • The bound for P is …• …deferred to the next episode