Complexity regularized pattern matching

We propose a technique that finds optimized descriptors for pattern matching applications. We formulate the pattern matching problem as the search of a pattern library for vectors defined in a query manifold. Our approach trades off the computational complexity involved in the search with matching accuracy by representing the query manifold with its complexity-dependent approximations. This is done in an optimal way so that a user with a given complexity budget accomplishes the optimal matching performance for that budget. Our work can be seen as defining a covering around the query manifold with the aid of the derived descriptors. The higher the allowed computational complexity, the tighter the covering, and the more accurate the match. Our formulation results in sparse descriptors which naturally emerge as the optimal solutions. The proposed descriptors are adaptively optimized for the particular search problem so that application-specific simplifications are taken full advantage of. Thanks to our algebraic approach, the presented formulation is general and can readily be applied to many different types of signals in addition to images and video.