Name
Abstract | ||
|---|---|---|
Let A and B be two colored point sets in R2, with |A| ≤ |B|. We propose a process for determining matches, in terms of the bottleneck distance, between A and subsets of B under color preserving rigid motion, assuming that the position of all colored points in both sets contains a certain amount of "noise". The process consists of two main stages: a lossless filtering algorithm and a matching algorithm. The first algorithm determines a number of candidate zones which are regions that contain a subset S of B such that A may match one or more subsets B′ of S. We use a compressed quadtree to have easy access to the subsets of B related to candidate zones and store geometric information that is used by the lossless filtering algorithm in each quadtree node. The second algorithm solves the colored point set matching problem: we generate all, up to a certain equivalence, possible motions that bring A close to some subset B′ of every S and seek for a matching between sets A and B&prime. To detect these possible matchings we use a bipartite matching algorithm that uses Skip Quadtrees for neighborhood queries. We have implemented the proposed algorithms and report results that show the efficiency of our approach. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-74472-6_3 | ICCSA (1) |
Keywords | Field | DocType |
matching algorithm,certain equivalence,candidate zone,possible matchings,subsets b,certain amount,subset b,point set,bipartite matching algorithm,proposed algorithm,bipartite matching | Prime (order theory),Mathematical optimization,Colored,Computer science,Bipartite graph,Filter (signal processing),3-dimensional matching,Blossom algorithm,Quadtree,Lossless compression | Conference |
Volume | ISSN | ISBN |
4705 | 0302-9743 | 3-540-74468-1 |
Citations | PageRank | References |
2 | 0.60 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yago Diez | 1 | 45 | 11.50 |
| J. Antoni Sellarès | 2 | 49 | 8.79 |