text: Feature-based object matching is a fundamental problem for many applications in computer vision, such as object recognition, 3D reconstruction, tracking, and motion segmentation. In this work, we consider simultaneously matching object instances in a set of images, where both inlier and outlier features are extracted. The task is to identify the inlier features and establish their consistent correspondences across the image set. This is a challenging combinatorial problem, and the problem complexity grows exponentially with the image number. To this end, we propose a novel framework, termed ROML, to address this problem. ROML optimizes simultaneously a partial permutation matrix (PPM) for each image, and feature correspondences are established by the obtained PPMs. Two of our key contributions are summarized as follows. (1) We formulate the problem as rank and sparsity minimization for PPM optimization, and treat simultaneous optimization of multiple PPMs as a regularized consensus problem in the context of distributed optimization. (2) We use the ADMM method to solve the thus formulated ROML problem, in which a subproblem associated with a single PPM optimization appears to be a difficult integer quadratic program (IQP). We prove that under wildly applicable conditions, this IQP is equivalent to a linear sum assignment problem (LSAP), which can be efficiently solved to an exact solution. Extensive experiments on rigid non-rigid object matching, matching instances of a common object category, and common object localization show the efficacy of our proposed method.
  @cite_23: Large classes of data association problems in multiple target tracking applications involving both multiple and single sensor systems can be formulated as multidimensional assignment problems. These NP-hard problems are large scale and sparse with noisy objective function values, but must be solved in “real-time”. Lagrangian relaxation methods have proven to be particularly effective in solving these problems to the noise level in real-time, especially for dense scenarios and for multiple scans of data from multiple sensors. This work presents a new class of constructive Lagrangian relaxation algorithms that circumvent some of the deficiencies of previous methods. The results of several numerical studies demonstrate the efficiency and effectiveness of the new algorithm class.
summary: Greedy approaches build a matching that has the lowest cost at each iteration, which has the obvious weakness that decisions once made, are fixed and may later be shown to be suboptimal. GRASP improves over greedy approaches by progressively constructing a list of best candidate matches and randomly selecting one from them. The process is repeated until all matches are exhausted. A final local search over the neighborhood of obtained matches may be used to further optimize the solution. In @cite_23 , Poore and Robertson presented a Lagrangian relaxation method that progressively relaxes the original and intermediate recovery MiAPs to linear assignment problems, by incorporating constraints of each MiAP into its objective function via the Lagrangian. However, this method involves implicitly enumerative procedure, and is difficult to implement and analyze.