GRAPH MATCHING WITH A DUAL-STEP EM ALGORITHM

This paper describes a new approach to matching geometric structure in 2D point-sets. The novel feature is to unify the tasks of estimating transformation geometry and identifying point-correspondence matches. Unification is realized by constructing a mixture model over the bipar tite graph representing the correspondence match and by affecting opti mization using the EM algorithm. According to our EM framework, the pr obabilities of structural correspondence gate contributions to the exp ected likelihood function used to estimate maximum likelihood transfor mation parameters. These gating probabilities measure the consistency of the matched neighborhoods in the graphs. The recovery of transforma tional geometry and hard correspondence matches are interleaved and ar e realized by applying coupled update operations to the expected log-l ikelihood function. In this way, the two processes bootstrap one anoth er. This provides a means of rejecting structural outliers. We evaluat e the technique on two real-world problems. The first involves the mat ching of different perspective views of 3.5-inch floppy discs. The sec ond example is furnished by the matching of a digital map against aeri al images that are subject to severe barrel distortion due to a line-s can sampling process. We complement these experiments with a sensitivi ty study based on synthetic data.