Analysis of Constrained Optimization Variants of the Map-Seeking Circuit Algorithm

摘要

The map-seeking circuit algorithm (MSC) was developed by Arathorn to efficiently solve the combinatorial problem of correspondence maximization, which arises in applications like computer vision, motion estimation, image matching, and automatic speech recognition (Arathorn, D.W. in Map-Seeking Circuits in Visual Cognition: A Computational Mechanism for Biological and Machine Vision, Stanford University Press, Stanford, 2002). Given an input image, a template image, and a discrete set of transformations, the goal is to find a composition of transformations which gives the best fit between the transformed input and the template. We imbed the associated combinatorial search problem within a continuous framework by using superposition, and we analyze a resulting constrained optimization problem. We present several numerical schemes to compute local solutions, and we compare their performance on a pair of test problems: an image matching problem and the challenging problem of automatically solving a Rubik’s cube.